speaker@umcp-cs.UUCP (11/02/83)
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
andree@uokvax.UUCP (11/09/83)
#R:umcp-cs:-352100:uokvax:900006:000:993 uokvax!andree Nov 4 15:14:00 1983 /***** uokvax:net.ai / umcp-cs!speaker / 9:41 pm Nov 1, 1983 */ 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! /* ---------- */ But I can do it with a one-tape, one-head turing machine. Let's assume that each of your 7 discrete sources can always be represeted in n bits. Thus, the total state of all seven sources can be represented in 7*n bits. My one-tape turing machine has 2 ** (7*n) symbols, so it can handle your 7 sources, each possible state of all 7 being one symbol of input. One of the things I did in an undergraduate theory course was show that an n-symbol turing machine is no more powerfull than a two-symbol turing machine for any finite (countable?) n. You just loose speed. <mike