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