Turing Compliant?
Stephan Houben
stephan at pcrm.win.tue.nl
Tue Sep 7 03:18:57 EDT 1999
Charles G Waldman <cgw at fnal.gov> writes:
> jhefferon at my-deja.com writes:
> > In article <oqpv02cq8v.fsf at titan.progiciels-bpi.ca>,
> > =?ISO-8859-1?Q?Fran=E7ois_Pinard?= <pinard at iro.umontreal.ca> wrote:
> > > A "simple" Turing machine has infinite memory. Who has that? :-)
> >
> > Not infinite. Unbounded.
> >
> > Jim Heffeorn
>
> Oh goody, it looks like we're about to have another long math
> tangent!
>
> I'd be interested to hear what the difference is, according to you,
> between "infinite" and "unbounded". According to me, they are the
> same thing. "finite"=="bounded" => !finite==!bounded.
Since you asked for it ... ;-)
A Turing machine performs a computation. During that computation,
it uses some amount of memory. Say it uses M units of memory.
Now, provided that the Turing machine terminates, M is always
finite. That's trivial, because the Turing machine terminated,
so it had only a finite time to use memory. So it can only
have sued a finite amount of memory.
However, if you come up with some number M, then I can construct
a Turing machine that will terminate and still use more memory than
M. This is true for every number M. Mathematically speaking,
the amount of memory required by a Turing machine is unbounded.
By the way, one mathematical game you can play with Turing machines
is to construct a Turing machine with, say, less than 4 states and
have it squander as much memory as possible, while still terminating.
IIRC, this is called a "busy beaver".
Alternatively, you can try to find upper bounds on the memory
consumption of a Turing machine with less than a certain number of states.
Greetings,
Stephan
More information about the Python-list
mailing list