Turing Compliant?

[Stephan Houben]

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