X-Message-Number: 9334
Date:  Sun, 22 Mar 98 12:19:27 
From: Mike Perry <>
Subject: Turing memory no problem

Thomas Donaldson, #9331:

>There is a problem in simply assuming that we can add more memory if
>our Turing machine runs short. To do so requires that we be able to
>predict the length of the computation it has been working on, which
>(if I understand rightly) is an unsolvable problem.

No, this is not a problem. You would just add memory as it's needed, 
in the course of the computation. 
No need to know in advance how much will be needed. In n steps a TM 
can only visit n squares. So to run the machine through n steps, you 
would have to have at most n extra memory cells to splice onto the 
tape. A "courteous" machine might even signal you when it ran out of 
tape and needed more to continue.

Mike Perry

Rate This Message: http://www.cryonet.org/cgi-bin/rate.cgi?msg=9334