[Overview] [Previous] [Next]

Formal Definition of Turing Machines

Important!A Turing machine M is a 7-tuple
(Q, sigma, gamma, delta, q0, #, F)
where Because the Turing machine has to be able to find its input, and to know when it has processed all of that input, we require:

Most other textbooks make no distinction between sigma (the input alphabet) and gamma (the tape alphabet). Our textbook does this to emphasize that the "input" (the nonblank symbols on the tape) does not contain #. Also, there may be more symbols in gamma than are present in the input.

Copyright 1996 by David Matuszek
Last modified Mar 24, 1996