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