home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / rec / puzzles / 8621 < prev    next >
Encoding:
Internet Message Format  |  1993-01-28  |  2.9 KB
  1. Path: sparky!uunet!das.wang.com!ulowell!m2c!nic.umass.edu!caen!spool.mu.edu!uwm.edu!cs.utexas.edu!qt.cs.utexas.edu!yale.edu!ira.uka.de!math.fu-berlin.de!news.netmbx.de!Germany.EU.net!mcsun!sunic!dkuug!diku!torbenm
  2. From: torbenm@diku.dk (Torben AEgidius Mogensen)
  3. Newsgroups: rec.puzzles
  4. Subject: Re: Turing Machines
  5. Message-ID: <1993Jan27.123943.2699@odin.diku.dk>
  6. Date: 27 Jan 93 12:39:43 GMT
  7. References: <1k2ltpINNs62@gap.caltech.edu> <C1GtHr.n7@mentor.cc.purdue.edu> <1k4cj8INNfst@gap.caltech.edu>
  8. Sender: torbenm@tyr.diku.dk
  9. Organization: Department of Computer Science, U of Copenhagen
  10. Lines: 48
  11.  
  12. sobelman@cco.caltech.edu (Steven M. Sobelman ) writes:
  13.  
  14. >ags@seaman.cc.purdue.edu (Dave Seaman) writes:
  15.  
  16. >>In article <1k2ltpINNs62@gap.caltech.edu> carl@SOL1.GPS.CALTECH.EDU (Carl  
  17. >>J Lydick) writes:
  18. >>> In article <728019101.AA05890@csource.oz.au>,  
  19. >>Ben.White@f364.n633.z3.fidonet.org (Ben White) writes:
  20. >>> >Has anyone here ever constructed a universal turing machine? 
  21. >>> I tried once, but I ran out of memory :-).  Seriously, by imposing the
  22. >>> adjective "universal," you've required that the machine have infinite  
  23. >>memory.
  24.  
  25. >>Wrong adjective. All turing machines, universal or not, have infinite  
  26. >>memory. 
  27.  
  28. >Actually, all turing machines have infinitely extensible memory which, in some
  29. >implementations, is represented by a tape.  If you have the necessary splicing
  30. >skills and can provide tape (or memory) faster than a UTM can use it, you,
  31. >effectively, have infinite memory.
  32.  
  33. >Building a UTM is a reasonably challenging task, I doubt it's been seriously
  34. >attempted.  I believe, however, that working non-universal TM's have been 
  35. >constructed.  They probably aren't very fast.
  36.  
  37. There are several ways to interpret the original question, depending
  38. one the exact meaning of "Turing machine". One can take it as a
  39. machine with a finite number of states and an infinite tape (Note that
  40. the "finite states" here refers to the number of "labels" or "program
  41. points" in the TM.  Counting the tape, any TM has an infinite number
  42. of states), or one can take it as a machine that is able to "load" any
  43. "program" that represents a finite state TM. The latter is often
  44. referred to as a universal TM, as it can calculate any computable
  45. (that is, partial recursive) function.
  46.  
  47. Another question is: is there a single finite state (in the sense
  48. above) TM that can compute all partial recursive functions? The answer
  49. is "Yes". von Neumann constructed a TM with only 6 states that can
  50. simulate any other TM by coding it's "program" on the tape together
  51. with it's initial input. Such a TM can can indeed be called
  52. "universal". In this sense: yes, someone has indeed constructed a
  53. universal Turing machine.
  54.  
  55. von Neumanns universal TM has incidentially been used to prove that 1
  56. dimensional cellular automata are universal: someone (I don't recall
  57. who) has constructed a 1D CA that simulates von Neumanns universal TM.
  58.  
  59.     Torben Mogensen (torbenm@diku.dk)
  60.