Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10 5/3/83; site umcp-cs.UUCP
Path: utzoo!linus!philabs!seismo!rlgvax!cvl!umcp-cs!speaker
From: speaker@umcp-cs.UUCP
Newsgroups: net.ai
Subject: Infinite loops and Turing machines...
Message-ID: <3521@umcp-cs.UUCP>
Date: Tue, 1-Nov-83 21:41:10 EST
Article-I.D.: umcp-cs.3521
Posted: Tue Nov  1 21:41:10 1983
Date-Received: Fri, 4-Nov-83 03:42:13 EST
Organization: Univ. of Maryland, Computer Science Dept.
Lines: 23


	One of the things I did in my undergrad theory class was to prove that
	a multiple-tape Turing machine is equivalent to one with a single tape
	(several tapes were very handy for programming).  Also, we showed that
	a TM with a 2-dimensional tape infinite in both x and y was also 
	equivalent to a single-tape TM.  On the other hand, the question of
	a machine with an infinite number of read heads was left open...
	
Aha!  I knew someone would come up with this one!
Consider that when we talk of simultaneous events... we speak of
simultaneous events that occur within one Turing machine state
and outside of the Turing machine itself.  Can a one-tape
Turing machine read the input of 7 discrete sources at once?
A 7 tape machine with 7 heads could!

The reason that they are not equivelent is that we have
allowed for external states (events) outside of the machine
states of the Turing machine itself.
-- 

					- Speaker-To-Stuffed-Animals
					speaker@umcp-cs
					speaker.umcp-cs@CSnet-Relay