Definition:Turing Machine

From ProofWiki
Jump to navigation Jump to search


Definition

A Turing machine is an idealization of a computing machine.

The idea goes as follows.

A Turing machine works by manipulating symbols on an imaginary piece of paper by means of a specific set of algorithmic rules.

To simplify things, the piece of paper being worked on is in the form of a series of boxes on a one-dimensional "tape" divided into squares.

Each square can be either blank or can contain a symbol taken from a finite set, e.g. $s_1, s_2, \ldots, s_\alpha$.


The machine examines one square at a time, and carries out an action determined by both:

$(1): \quad$ the symbol in the square
$(2): \quad$ the current internal state of the machine.

The internal state of the machine is a way of providing a device that can keep track of the symbols in other squares.

There can be only a finite set of these states, say $q_1, q_2, \ldots, q_\beta$.


The actions that the machine can take are as follows:

$(1): \quad$ Replace the symbol in the square with another symbol
$(2): \quad$ Move to examine the square in the immediate left of the current square being looked at
$(3): \quad$ Move to examine the square in the immediate right of the current square being looked at.

After carrying out an action, the machine may change to a different internal state.


The program for the machine is a set of instructions which specify:

$(1): \quad$ what action to take in some possible combinations of the internal state and symbol in the square currently being read
$(2): \quad$ which internal state the machine moves into after carrying out that action.

Thus the instructions have the following form:

$q_i \quad s_j \quad A \quad q_t$

which is interpreted as:

"If:

  • the machine is in internal state $q_i$
the symbol in the square currently being examined is $s_j$

then:

Carry out action $A$
Move into internal state $q_t$.


The actions can be abbreviated to:

$L$: Move one square to the left
$R$: Move one square to the right
$s_k$: Replace the symbol in the square currently being read with symbol $s_k$.


The computation stops when there is no instruction which specifies what should be done in the current combination of internal state and symbol being read.


Also known as

Such a machine is also known as a deterministic Turing machine to distinguish it from the nondeterministic version.


Also see

  • Results about Turing machines can be found here.


Source of Name

This entry was named for Alan Mathison Turing.


Historical Note

The Turing machine was devised by Alan Mathison Turing some time around $1936$.


Sources