X-Message-Number: 8533
Date: Thu, 04 Sep 1997 08:55:36 -0400
From: "John P. Pietrzak" <>
Subject: On the Turing Machine
References: <>

Hi Thomas

There's a few ideas floating around about Turing Machines that I don't
think are quite on target here.

[on parallel computers]
> These hardly classify as Turing machines because they have more than
> one processor (though we can criticise the idea in other ways too).
> But parallel computers or circuitry (like the MMX that Intel is so
> proud of) become so pertinent not for theoretical reasons but for
> very practical ones: if we tried to make a true Turing machine to
> do the calculations which a large Intel Paragon might do, we'd not
> live long enough for the Turing machine to complete those
> calculations.

Hang on a minute here.  The Turing Machine is a theoretical device,
a simplified concept of what it means to compute, not an actual
suggestion as to how a processor should be implemented.  Roughly
speaking, it has the notion of a program (a finite state automata
controlling the tape head) and external storage (the tape itself).
The program can basically do anything any modern processor does
(you can make the FSA as complicated as you want, so long as it is
finite) and the external storage can store anything you want (the
tape is as long as you need).  Therefore, any constraints you can
prove apply to the Turing Machine should also apply to any modern
computer.

Of course, the stupid thing is so simple that any actual attempt to
mimic it directly in physical hardware would undoubtably produce an
incredibly slow machine.  But that's not the point.

I believe that there is some permutation of the Turing Machine that
is of use in proving theorems about parallel computation.  (I'm pretty
certain that it is still equivalent to the generic Turing Machine, but
I can't remember exactly.  I'll have to look it up.)


John

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