[Overview] [Previous] [Next]

Transition Function, Instantaneous Descriptions, and Moves

The transition function for Turing machines is given by

delta: Q cross product gamma goes to Q cross product gamma cross product {L, R}

This means:
When the machine is in a given state (Q) and reads a given symbol (gamma) from the tape, it replaces the symbol on the tape with some other symbol (gamma), goes to some other state (Q), and moves the tape head one square left (L) or right (R).

An instantaneous description or configuration of a Turing machine requires (1) the state the Turing machine is in, (2) the contents of the tape, and (3) the position of the tape head on the tape. This can be summarized in a string of the form


where the x's are the symbols on the tape, qm is the current state, and the tape head is on the square containing xk (the symbol immediately following qm).

A move of a Turing machine can therefore be represented as a pair of instaneous descriptions, separated by the symbol "move to". For example, if

delta(q5, b) = (q8, c, R)
then a possible move might be
abbabq5babb move to abbabcq8abb

Copyright 1996 by David Matuszek
Last modified Mar 25, 1996