X-Message-Number: 8534 Date: Thu, 04 Sep 1997 09:41:00 -0400 From: "John P. Pietrzak" <> Subject: A formal definiton of the Turing Machine References: <> > Again, more precision is needed when we talk about a computer, even > the simple kind Turing set up. You asked for it. :) :) From "Introduction to Automata Theory, Languages, and Computation" by Hopcroft & Ullman, Addison-Wesley Publishing Co., 1979, p. 148 : "Formally, a Turing machine M is denoted M = (Q, Sigma, Lambda, delta, q0, B, F), where Q is the finite set of states, Lambda is the finite set of allowable tape symbols, B, a symbol of Lambda, is the blank, Sigma, a subset of Lambda not including B, is the set of input symbols, delta is the next move function, a mapping from Q X Lambda to Q X Lambda X {Left, Right}, q0, a state of Q, is the start state, and F, a subset of Q, is the set of final states." Basically, in this definition, Q, q0, and F make up the structure of an ordinary deterministic finite state automata; Lambda, B, and Sigma are the structures used to describe the tape (data on the tape being made up of sequences of symbols from Sigma separated from each other by one or more Bs); and delta is the glue which ties the DFSA to the tape. I can give more detail if desired. Actually, Hopcroft & Ullman's book is really pretty good, even being that it's almost 20 years old now; anyone interested in automata theory over the Chomsky hierarchy should give it a look-see. As to extending this model to analog computing, as Thomas suggests, I have no idea. Thomas' system basically replaces the finite set of tape symbols (Lambda) with an infinite set of tape symbols (corresponding to the real numbers). The problem here is, in the analog machines I've seen, the control was analog along with the data; requiring, essentially, a "non-finite" state automata to control the tape head (assuming that the whole idea doesn't break down here). I haven't really thought about analog machines in years. I'm going to have to head out to the library and see if I can't dig up some material on their construction. John Rate This Message: http://www.cryonet.org/cgi-bin/rate.cgi?msg=8534