X-Message-Number: 9331
From: Thomas Donaldson <>
Subject: more.re.Turing.machines
Date: Sat, 21 Mar 1998 01:27:24 -0800 (PST)

and for devotees of Turing machines, one further comment:

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. Nor can the Turing machine predict the
length of its computation: one more unsolvable problem. It cannot even
decide that it needs more tape until it runs out and therefore simply
halts. No doubt starting it over with a longer tape will let it go on
longer, and eventually we find that its computation ends. But that hardly
seems a very efficient procedure. We have no way of knowing in advance
just how long a tape it will need, and would have to find out by trial 
and error. Is this really the model of computation that we want? 

Any serious theory of computing, which aims to deal with real computation
rather than purely theoretical computation, will have to use finite machines.
If they are finite, some obvious restrictions occur that a theoretically
infinite machine will not have. This is, after all, hardly surprising.

I'll also add that as a constructivist in mathematics it's been quite
possible to develop real mathematics, up to DEs and metric spaces at least,
with entirely constructive, finite arguments in which suppositions of 
infinity play no role. Considering the florid growth of computing, a
decision to limit ourselves to finite machines will probably limit even 
our theories of computation at worst by a trivial amount. And in return,
we would have a much deeper idea of what is really possible.

			Best wishes and long long life to all,

				Thomas Donaldson

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