On 1998-03-10 classiccmp_at_u.washington.edu said to lisard_at_zetnet.co.uk
:It's been a long time since I've looked at a CS book, but I
:remember the Turing machine as a *theoretical* machine that reads
:and writes symbols on an *infinitely long* tape. I'm sure somebody
:could build an approximation of this, but the main interest in the
:Turing machine is that it is used as the definition of
:computational "power." One of theories is that no machine built
:today, or at any time in the future, no matter what the
:architecture, will be able to compute anything that a simple Turing
:machine cannot compute..
that's the one. alan turing defined these machines as part of his
contribution to the proof that mathematics has some unprovables.
anything that can be proved, period, can be proved by a turing machine;
anything that a turing machine can't prove is unprovable. kurt godel
(most famously, perhaps?) and alonzo church producd alternative theorems
to demonstrate the same thing, but turing's work laid the basis for
computer science, and turing himself became quite active within the
field of early uk computation (the original ACE design is his, and he
subsequently worked on manchester's computers).
there are even such things as "universal turing machines", which can be
given definitions of turing machines and used to solve such problems,
which we suspect led directly on to universal computers which could be
programmed to simulate special purpose devices.
the "infinite tape" idea is as important as you suggested, however.
--
Communa (together) we remember... we'll see you falling
you know soft spoken changes nothing to sing within her...
Received on Wed Mar 11 1998 - 13:35:16 GMT