Definition:Turing Machine

From ProofWiki
Jump to navigation Jump to search


This page has been identified as a candidate for refactoring of advanced complexity.
In particular: There are several internal definitions in here: program, internal state, etc. Each could be extracted and put into its own page.
Until this has been finished, please leave {{Refactor}} in the code.

New contributors: Refactoring is a task which is expected to be undertaken by experienced editors only.

Because of the underlying complexity of the work needed, it is recommended that you do not embark on a refactoring task until you have become familiar with the structural nature of pages of $\mathsf{Pr} \infty \mathsf{fWiki}$.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{Refactor}} from the code.


Definition

A Turing machine is an abstract machine which 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.

Formal Definition


This page needs proofreading.
In particular: This might be too detailed or difficult to read, not to mention possible errors.
If you believe all issues are dealt with, please remove {{Proofread}} from the code.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{Proofread}} from the code.


A Turing machine is a 7-tuple $\paren {Q, \Sigma, \Gamma, \delta, q_0, B, F}$ that satisfies the following:

  • $Q$ is a finite set, the states of the machine.
  • $\Sigma$ is a finite set, the input symbols.
  • $\Gamma \supsetneq \Sigma$ is a finite superset of the input symbols, called the tape symbols.
    • For convenience, we also require that $\Gamma$ and $Q$ are disjoint.
  • $\delta : Q \times \Gamma \to Q \times \Gamma \times \set {L, R}$ is a partial mapping, the transition function.
    • $L$ and $R$ are arbitrary constants called directions.
  • $q_0 \in Q$ is a distinguished state called the start state.
  • $B \in \Gamma$ is a distinguished tape symbol called the blank symbol. $B$ must not be an element of $\Sigma$.
  • $F \subset Q$ be a designated subset of the states called accepting states.


An instantaneous description of a Turing machine is a finite sequence of elements of $\Gamma \cup Q$, subject to the following conditions:

  • There is exactly one element of $Q$ in the sequence.
  • The first entry in the sequence is not $B$.
  • The last entry in the sequence is not in $Q$.
  • If the last entry in the sequence is $B$, then the second-to-last is in $Q$.

By this definition, an instantaneous description can always be written as:

$X_m X_{m-1} \dotsm X_2 X_1 q Y Z_1 Z_2 \dotsm Z_{n-1} Z_n$

where $m$ or $n$ may be $0$; $X_i$, $Y$, and $Z_j$ are all elements of $\Gamma$; and $q$ is an element of $Q$.

Additionally, $X_m$ and $Z_n$ are not $B$ if they exist; that is, if $m$ and $n$ are not $0$, respectively.


A move reduces one instantaneous description into another by applying the transition function.

We write $A \vdash B$ if a machine with instantaneous description $A$ has, after a single move, instantaneous description $B$.

Let $\map \delta {q, Y} = \paren{q', Y', d}$.

Then there are seven cases to consider:

  • If $d = L$ and $m > 0$, and either $n > 0$ or $Y' \neq B$ then:
$X_m \dotsm X_2 X_1 q Y Z_1 \dotsm Z_n \vdash X_m \dotsm X_2 q' X_1 Y' Z_1 \dotsm Z_n$
  • If $d = L$ and $m > 0$, but $n = 0$ and $Y' = B$ then:
$X_m \dotsm X_2 X_1 q Y \vdash X_m \dotsm X_2 q' X_1$
  • If $d = L$ but $m = 0$, and either $n > 0$ or $Y' \neq B$ then:
$q Y Z_1 \dotsm Z_n \vdash q' B Y' Z_1 \dotsm Z_n$
  • If $d = R$ and $n > 0$, and either $m > 0$ or $Y' \neq B$ then:
$X_m \dotsm X_1 q Y Z_1 Z_2 \dotsm Z_n \vdash X_m \dotsm X_1 Y' q' Z_1 Z_2 \dotsm Z_n$
  • If $d = R$ and $n > 0$, but $m = 0$ and $Y' = B$ then:
$q Y Z_1 Z_2 \dotsm Z_n \vdash q' Z_1 Z_2 \dotsm Z_n$
  • If $d = R$ but $n = 0$, and either $m > 0$ or $Y' \neq B$ then:
$X_m \dotsm X_1 q Y \vdash X_m \dotsm X_1 Y' q' B$
  • If $m = 0$, $n = 0$, and $Y' = B$ then regardless of $d$:
$q Y \vdash q' B$


Let $A \vdash^* B$ indicate that there exists a finite sequence $\sequence {A_i}_{0 \leq i \leq n}$ such that:

$A = A_0 \vdash A_1 \vdash A_2 \vdash \dotso \vdash A_n = B$


The language $\map L M$ accepted by the machine $M$ is the set of strings $w \in \Sigma^*$ for which, for some $\alpha, \beta \in \Gamma^*$ and $p \in F$:

$q_0 w \vdash^* \alpha p \beta$

As a special case, the null string is in the language if and only if the above holds for $w = B$.


A machine $M$ halts on an input $w$, using the same special case for the null string as above, if and only if for some $\alpha, \beta \in \Gamma^*$, $X \in \Gamma$, and $q \in Q$:

$q_0 w \vdash^* \alpha q X \beta$

where $\map \delta {q, X}$ is undefined.


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

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Turing_Machine&oldid=624547"