home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / rec / puzzles / 8585 < prev    next >
Encoding:
Internet Message Format  |  1993-01-28  |  1.5 KB
  1. Path: sparky!uunet!stanford.edu!ames!elroy.jpl.nasa.gov!nntp-server.caltech.edu!sobelman
  2. From: sobelman@cco.caltech.edu (Steven M. Sobelman )
  3. Newsgroups: rec.puzzles
  4. Subject: Re: Turing Machines
  5. Date: 26 Jan 1993 22:05:27 GMT
  6. Organization: California Institute of Technology, Pasadena
  7. Lines: 26
  8. Message-ID: <1k4cj8INNfst@gap.caltech.edu>
  9. References: <1k2ltpINNs62@gap.caltech.edu> <C1GtHr.n7@mentor.cc.purdue.edu>
  10. NNTP-Posting-Host: sandman.caltech.edu
  11.  
  12. ags@seaman.cc.purdue.edu (Dave Seaman) writes:
  13.  
  14. >In article <1k2ltpINNs62@gap.caltech.edu> carl@SOL1.GPS.CALTECH.EDU (Carl  
  15. >J Lydick) writes:
  16. >> In article <728019101.AA05890@csource.oz.au>,  
  17. >Ben.White@f364.n633.z3.fidonet.org (Ben White) writes:
  18. >> >Has anyone here ever constructed a universal turing machine? 
  19. >> I tried once, but I ran out of memory :-).  Seriously, by imposing the
  20. >> adjective "universal," you've required that the machine have infinite  
  21. >memory.
  22.  
  23. >Wrong adjective. All turing machines, universal or not, have infinite  
  24. >memory. 
  25.  
  26. Actually, all turing machines have infinitely extensible memory which, in some
  27. implementations, is represented by a tape.  If you have the necessary splicing
  28. skills and can provide tape (or memory) faster than a UTM can use it, you,
  29. effectively, have infinite memory.
  30.  
  31. Building a UTM is a reasonably challenging task, I doubt it's been seriously
  32. attempted.  I believe, however, that working non-universal TM's have been 
  33. constructed.  They probably aren't very fast.
  34.  
  35.  
  36. Steve
  37.  
  38.