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:

    “The formal Washington dinner party has all the spontaneity of a Japanese imperial funeral.”
    —Simon Hoggart (b. 1946)

    “It’s a rare parent who can see his or her child clearly and objectively. At a school board meeting I attended . . . the only definition of a gifted child on which everyone in the audience could agree was “mine.””
    —Jane Adams (20th century)