Article View: rec.puzzles
Article #2587Re: Turing Machines
From: Steven M. Sobelman
Date: Tue, 26 Jan 1993 22:05
Date: Tue, 26 Jan 1993 22:05
25 lines
1525 bytes
1525 bytes
ags@seaman.cc.purdue.edu (Dave Seaman) writes: >In article <1k2ltpINNs62@gap.caltech.edu> carl@SOL1.GPS.CALTECH.EDU (Carl >J Lydick) writes: >> In article <728019101.AA05890@csource.oz.au>, >Ben.White@f364.n633.z3.fidonet.org (Ben White) writes: >> >Has anyone here ever constructed a universal turing machine? >> I tried once, but I ran out of memory :-). Seriously, by imposing the >> adjective "universal," you've required that the machine have infinite >memory. >Wrong adjective. All turing machines, universal or not, have infinite >memory. Actually, all turing machines have infinitely extensible memory which, in some implementations, is represented by a tape. If you have the necessary splicing skills and can provide tape (or memory) faster than a UTM can use it, you, effectively, have infinite memory. Building a UTM is a reasonably challenging task, I doubt it's been seriously attempted. I believe, however, that working non-universal TM's have been constructed. They probably aren't very fast. Steve
Technical Details
Message-ID:
<1k4cj8INNfst@gap.caltech.edu>Path:
arc1-ca.pugleaf.net!sparky!uunet!stanford.edu!ames!elroy.jpl.nasa.gov!nntp-server.caltech.edu!sobelmanReferences:
<1k2ltpINNs62@gap.caltech.edu> <C1GtHr.n7@mentor.cc.purdue.edu>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!sparky!uunet!stanford.edu!ames!elroy.jpl.nasa.gov!nntp-server.caltech.edu!sobelman From: sobelman@cco.caltech.edu (Steven M. Sobelman ) Newsgroups: rec.puzzles Subject: Re: Turing Machines Date: 26 Jan 1993 22:05:27 GMT Organization: California Institute of Technology, Pasadena Lines: 26 Message-ID: <1k4cj8INNfst@gap.caltech.edu> References: <1k2ltpINNs62@gap.caltech.edu> <C1GtHr.n7@mentor.cc.purdue.edu> NNTP-Posting-Host: sandman.caltech.edu