Turing Machine - Formal Definition

Formal Definition

Hopcroft and Ullman (1979, p. 148) formally define a (one-tape) Turing machine as a 7-tuple where

  • is a finite, non-empty set of states
  • is a finite, non-empty set of the tape alphabet/symbols
  • is the blank symbol (the only symbol allowed to occur on the tape infinitely often at any step during the computation)
  • is the set of input symbols
  • is the initial state
  • is the set of final or accepting states.
  • is a partial function called the transition function, where L is left shift, R is right shift. (A relatively uncommon variant allows "no shift", say N, as a third element of the latter set.)

Anything that operates according to these specifications is a Turing machine.

The 7-tuple for the 3-state busy beaver looks like this (see more about this busy beaver at Turing machine examples):

  • ("blank")
  • (the initial state)
  • see state-table below

Initially all tape cells are marked with 0.

State table for 3 state, 2 symbol busy beaver
Tape symbol Current state A Current state B Current state C
Write symbol Move tape Next state Write symbol Move tape Next state Write symbol Move tape Next state
0 1 R B 1 L A 1 L B
1 1 L C 1 R B 1 R HALT

Read more about this topic:  Turing Machine

Famous quotes containing the words formal and/or definition:

    “On every formal visit a child ought to be of the party, by way of provision for discourse.”
    —Jane Austen (1775–1817)

    “... we all know the wag’s definition of a philanthropist: a man whose charity increases directly as the square of the distance.”
    —George Eliot [Mary Ann (or Marian)