[Overview] [Previous] [Next]

Turing Machines as Acceptors

Important!A Turing machine halts when it no longer has any available moves. If it halts in a final state, it accepts its input; otherwise, it rejects its input.

This is too easy, so let's repeat it in symbols:

A Turing Machine T = (Q, sigma, gamma, delta, q0, #, F) accepts a language L(M), where

L(M) = (w is a member of sigma+: q0w move zero or more times to xiqfxj
for some qf is a member of F, xi, xj is a member of gamma*}

(Notice that this definition assumes that the Turing machine starts with its tape head positioned on the leftmost symbol.)

Important!We said a Turing machine accepts its input if it halts in a final state. There are two ways this could fail to happen:

  1. The Turing machine could halt in a nonfinal state, or
  2. The Turing machine could never stop (in which case we say it is in an infinite loop. )
If a Turing machine halts, the sequence of configurations leading to the halt state is called a computation.

Copyright 1996 by David Matuszek
Last modified Mar 25, 1996