Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!batcomputer!cornell!rochester!udel!haven.umd.edu!socrates.umd.edu!socrates!rockwell
From: rockwell@socrates.umd.edu (Raul Rockwell)
Newsgroups: comp.lang.misc
Subject: Re: Will this *thread* ever halt?
Message-ID: <ROCKWELL.91May29190859@socrates.umd.edu>
Date: 30 May 91 00:08:59 GMT
References: <31051@dime.cs.umass.edu> <k3ZN38w164w@mantis.co.uk> <31195@dime.cs.umass.edu>
Sender: rockwell@socrates.umd.edu (Raul Rockwell)
Organization: Traveller
Lines: 37
In-Reply-To: yodaiken@chelm.cs.umass.edu's message of 29 May 91 04: 04:57 GMT

Victor Yodaiken:
   \begin{quote}
   Turing machines are widely considered to be the abstract prototype
   of digital computers; workers in the field, however, have felt more
   and more that the notion of a Turing machine is too general to
   serve as an accurate model of actual computers. It is well known
   that for even a simple calculation it is impossible to give an 
   {\it a priori} upper bound on the amount of tape a Turing machine
   will neeed for any given computation. It is precisely this feature
   which renders Turing's concept unrealistic.
   \end{quote}

   author="Rabin M.O. and Dana Scott",
[etc...]

While this quote may be literally accurate (workers in the field have
felt...) it misses what I feel is a rather major point:

 The reason it is impossible to give an upper bound of tape on a
 Turing machine for a given computation is because these computations
 are traditionally expressed for *arbitrarily large objects*.  If any
 object can be arbitrarily large then it doesn't matter WHAT the
 computation is, it will take an arbitrarily large amount of tape to
 represent the computation on that object.

Note that if you limit your objects to some finite size (like,
integers whose absolute magnitude is less than 2 billion), you can
represent (for example) multiplication of two of these numbers using
only two tape cells.  Of course, then you have to deal with overflow
conditions, but that's a problem with any finite number
representation.

Note that you do *not* want to write out each of the quadrapoles by
hand for this kind of turing machine--so don't.  Just use
parameterized descriptions.

Raul Rockwell