Path: utzoo!attcan!uunet!lll-winken!lll-tis!ames!mailrus!cornell!blandy
From: blandy@awamore.cs.cornell.edu (Jim Blandy)
Newsgroups: comp.sys.amiga
Subject: What's a TM?
Message-ID: <19918@cornell.UUCP>
Date: 3 Aug 88 04:49:48 GMT
Sender: nobody@cornell.UUCP
Reply-To: blandy@cs.cornell.edu (Jim Blandy)
Organization: Cornell Univ. CS Dept, Ithaca NY
Lines: 44

I see now that I should have shar'ed them together.  Sorry.  Next time.

Since a certain well-known Amiga hacker has told me he doesn't know
what a Turing machine is, I guess they're not as well-known as I
thought they were.  I thought that maybe a short explanation would
help make my other posting that much more interesting.  Saving
bandwidth by making it useful, or something...  This is an explanation
of Turing machines to accompany my DME Turing machine simulator.

Suppose you wanted to prove a theorem about what kind of calculations
an Amiga could or could not do.  The Amiga's a complicated machine, a
real pain in the neck to prove anything about.  Even if you succeeded,
you would only have proved it about your Amiga with your hardware
running your software.  You'd have to do it all over again for a VAX.

So a TM is a VERY SIMPLE computer, simple enough to write proofs
about, but powerful enough to do anything any computer can do.  It's
been proven already that anything a TM can do, a computer can do, and
vice versa.

A TM reads from and writes to a tape; depending on what state it's in
and what character is under its read/write head, it 1) writes a new
character, 2) moves the tape head right or left one space, and 3) goes
into a new state.  This repeats until the TM hits a character it
doesn't know what to do with.  Programming a TM consists of telling it
what it should do in a particular state on a particular character; you
tell it when to stop by letting it crash, as described above.  Note
that the tape has a left end, but is infinitely long to the right;
everything to the right of the characters on the tape is filled with
blanks.

For example, suppose you wanted your TM to evaluate an expression.
You'd program the TM, put the expression on the tape, and start it up.
Most likely the TM would use the blank tape after the expression for
intermediate results.  The TM would work back and forth for a while,
and when it finished, it would leave the answer on the tape.

The two sample TMs included with the program show typical strategies
for solving simple problems; some approaches are more complicated...

Have fun.  I thought enough people might find it amusing to make it of
general interest.
--
Jim Blandy - blandy@crnlcs.bitnet
"And now," cried Max, "let the wild rumpus start!"