home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / rec / puzzles / 8625 < prev    next >
Encoding:
Internet Message Format  |  1993-01-28  |  1.8 KB
  1. Path: sparky!uunet!ogicse!das-news.harvard.edu!husc-news.harvard.edu!birkhoff!kubo
  2. From: kubo@birkhoff.harvard.edu (Tal Kubo)
  3. Newsgroups: rec.puzzles
  4. Subject: Re: Turing Machines
  5. Message-ID: <1993Jan27.164126.19870@husc3.harvard.edu>
  6. Date: 27 Jan 93 21:41:25 GMT
  7. Article-I.D.: husc3.1993Jan27.164126.19870
  8. References: <C1GtHr.n7@mentor.cc.purdue.edu> <1k4cj8INNfst@gap.caltech.edu> <1993Jan27.123943.2699@odin.diku.dk>
  9. Organization: Dept. of Math, Harvard Univ.
  10. Lines: 28
  11. Nntp-Posting-Host: birkhoff.harvard.edu
  12.  
  13. In article <1993Jan27.123943.2699@odin.diku.dk> 
  14. torbenm@diku.dk (Torben AEgidius Mogensen) writes: 
  15. >
  16. >von Neumann constructed a TM with only 6 states that can
  17. >simulate any other TM by coding it's "program" on the tape together
  18. >with it's initial input. Such a TM can can indeed be called
  19. >"universal". In this sense: yes, someone has indeed constructed a
  20. >universal Turing machine.
  21.  
  22. Minsky has constructed of universal TM's with various small values 
  23. of the pair (number of states, size of alphabet).  See his book 
  24. "Computation: Finite and Infinite Machines".  Some of the values
  25. were surprisingly small, with both numbers being less than 10.
  26. Minsky's book is pretty old, and the state of the art may have advanced
  27. since it was published.
  28.  
  29. >von Neumanns universal TM has incidentially been used to prove that 1
  30. >dimensional cellular automata are universal: someone (I don't recall
  31. >who) has constructed a 1D CA that simulates von Neumanns universal TM.
  32.  
  33. I think it was Alvy Ray Smith's PhD thesis sometime in the
  34. 1970's. This was mentioned in an old Martin Gardner column 
  35. on the game of Life (which is itself a universal 2DCA) .  
  36. If memory serves, Smith's universal 1DCA  had an  alphabet 
  37. of 239 symbols.   Does anyone have more references on this
  38. subject?
  39.  
  40. Tal   kubo@math.harvard.edu
  41.