Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!linus!security!genrad!decvax!microsoft!uw-beaver!cornell!vax135!ariel!houti!hogpc!drux3!ihnp4!inuxc!pur-ee!uiucdcs!uokvax!andree From: andree@uokvax.UUCP Newsgroups: net.ai Subject: Re: Infinite loops and Turing machines.. - (nf) Message-ID: <3712@uiucdcs.UUCP> Date: Tue, 8-Nov-83 23:03:04 EST Article-I.D.: uiucdcs.3712 Posted: Tue Nov 8 23:03:04 1983 Date-Received: Fri, 11-Nov-83 22:28:37 EST Lines: 23 #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.