🚀 go-pugleaf

sobelman@cco.caltech.edu (Steven M. Sobelman ) writes:

>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.

There are several ways to interpret the original question, depending
one the exact meaning of "Turing machine". One can take it as a
machine with a finite number of states and an infinite tape (Note that
the "finite states" here refers to the number of "labels" or "program
points" in the TM.  Counting the tape, any TM has an infinite number
of states), or one can take it as a machine that is able to "load" any
"program" that represents a finite state TM. The latter is often
referred to as a universal TM, as it can calculate any computable
(that is, partial recursive) function.

Another question is: is there a single finite state (in the sense
above) TM that can compute all partial recursive functions? The answer
is "Yes". von Neumann constructed a TM with only 6 states that can
simulate any other TM by coding it's "program" on the tape together
with it's initial input. Such a TM can can indeed be called
"universal". In this sense: yes, someone has indeed constructed a
universal Turing machine.

von Neumanns universal TM has incidentially been used to prove that 1
dimensional cellular automata are universal: someone (I don't recall
who) has constructed a 1D CA that simulates von Neumanns universal TM.

	Torben Mogensen (torbenm@diku.dk)