Re: Turing Machines and Physical Computation
From: Stephen Harris (cyberguard1048-usenet_at_yahoo.com)
Date: 12/09/04
- Previous message: Stephen Harris: "Re: Reduce from X to "maximum acyclic subgraph"?"
- In reply to: Kent Paul Dolan: "Re: Turing Machines and Physical Computation"
- Next in thread: examachine_at_gmail.com: "Re: Turing Machines and Physical Computation"
- Reply: examachine_at_gmail.com: "Re: Turing Machines and Physical Computation"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Thu, 09 Dec 2004 01:14:24 GMT
"Kent Paul Dolan" <xanthian@well.com> wrote in message
news:912f820c9e968fa05d80319259ecd227.48257@mygate.mailgate.org...
> "Albert van der Horst" <albert@spenarnc.xs4all.nl> wrote:
>
>> The wording is a bit metaphysical. This problem
>> is such that for each N there is an instance of a
>> language item wherefore a dedicated TM will need a
>> tape that is larger than N. Actual infinity
>> doesn't enter the picture.
>
> So it must be bigger than any such size, and a tape
> that is bigger than every finite size you can name
> even in concept is an infinite tape.
>
I've read Turing's 1936 paper several times and this is
not my understanding. The idea that comes closest to
an infinite tape is a TM that never halts due to undecidability.
All decidable problems have a finite number of computations.
A TM computes Pi, which has an infinite expansion, one finite
digit at a time. So the common terminology is "potentially infinite".
A maxed out memory PC can compute Pi to about 10^230 digits,
a finite number of digits. A TM can compute Pi to 10^230000000
digits, or greater, any huge finitely specified degree of expansion.
I have not seen the idea that a TM computes the last digit of Pi
because it computes for an infinite amount of time. There is a
strong argument to describe a TM as "finintely unbounded" rather
"potentially infinite". The TM tape grows towards infinity but
does not start off as infinitely long. The tape to add 1 + 1 will
be very short. The "length" of the tape is dependent upon the
size of the input. A TM does not complete the computation of Pi.
The digits on the tape become finitely larger, and there are always
a finite number of digits on the tape, one finite step at a time.
The purpose of the limitless tape is so that a TM will not halt
too soon due to running out of tape, and thus indicate decidability,
whereas if it has endless tape, the same computation might have
been undecidable. The endless tape insures, that if the TM halts,
it is due to being decidable, not an issue of insufficient tape.
I search Turing's 1936 paper and only found the word "infinite"
in reference in the ink supply.
Kent wrote:
"So it must be bigger than any such size, and a tape
that is bigger than every finite size you can name
even in concept is an infinite tape." [SH: finitely unbounded]
SH: No it is a larger finite tape for each larger finite computation
specified.
There is no bound or upper limit to the finite specification. The TM can
actually never complete the computation of infinity, or the infinite digit
expansion of Pi (which is computable). But the TM can approach the
limit of infinity while not becoming infinity. Meaning the TM using a
tape to express the digits of Pi. There is no sense of a completed,
actualized infinity, like as if all the digits of Pi could be computed by a
TM.
In the paper you will see Turing's emphasis is on the finite.
- Previous message: Stephen Harris: "Re: Reduce from X to "maximum acyclic subgraph"?"
- In reply to: Kent Paul Dolan: "Re: Turing Machines and Physical Computation"
- Next in thread: examachine_at_gmail.com: "Re: Turing Machines and Physical Computation"
- Reply: examachine_at_gmail.com: "Re: Turing Machines and Physical Computation"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
