home *** CD-ROM | disk | FTP | other *** search
/ Club Amiga de Montreal - CAM / CAM_CD_1.iso / files / 171.lha / DME_v1.30 / Notes < prev    next >
Internet Message Format  |  1988-04-28  |  2KB
  1. From: blandy@awamore.cs.cornell.edu (Jim Blandy)
  2. Subject: What's a TM?
  3. Date: 3 Aug 88 04:49:48 GMT
  4. Organization: Cornell Univ. CS Dept, Ithaca NY
  5.  
  6.  
  7. I see now that I should have shar'ed them together.  Sorry.  Next time.
  8.  
  9. Since a certain well-known Amiga hacker has told me he doesn't know
  10. what a Turing machine is, I guess they're not as well-known as I
  11. thought they were.  I thought that maybe a short explanation would
  12. help make my other posting that much more interesting.    Saving
  13. bandwidth by making it useful, or something...    This is an explanation
  14. of Turing machines to accompany my DME Turing machine simulator.
  15.  
  16. Suppose you wanted to prove a theorem about what kind of calculations
  17. an Amiga could or could not do.  The Amiga's a complicated machine, a
  18. real pain in the neck to prove anything about.    Even if you succeeded,
  19. you would only have proved it about your Amiga with your hardware
  20. running your software.    You'd have to do it all over again for a VAX.
  21.  
  22. So a TM is a VERY SIMPLE computer, simple enough to write proofs
  23. about, but powerful enough to do anything any computer can do.    It's
  24. been proven already that anything a TM can do, a computer can do, and
  25. vice versa.
  26.  
  27. A TM reads from and writes to a tape; depending on what state it's in
  28. and what character is under its read/write head, it 1) writes a new
  29. character, 2) moves the tape head right or left one space, and 3) goes
  30. into a new state.  This repeats until the TM hits a character it
  31. doesn't know what to do with.  Programming a TM consists of telling it
  32. what it should do in a particular state on a particular character; you
  33. tell it when to stop by letting it crash, as described above.  Note
  34. that the tape has a left end, but is infinitely long to the right;
  35. everything to the right of the characters on the tape is filled with
  36. blanks.
  37.  
  38. For example, suppose you wanted your TM to evaluate an expression.
  39. You'd program the TM, put the expression on the tape, and start it up.
  40. Most likely the TM would use the blank tape after the expression for
  41. intermediate results.  The TM would work back and forth for a while,
  42. and when it finished, it would leave the answer on the tape.
  43.  
  44. The two sample TMs included with the program show typical strategies
  45. for solving simple problems; some approaches are more complicated...
  46.  
  47. Have fun.  I thought enough people might find it amusing to make it of
  48. general interest.
  49. --
  50. Jim Blandy - blandy@crnlcs.bitnet
  51. "And now," cried Max, "let the wild rumpus start!"
  52.  
  53.