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 $T$ 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 Turing 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.


Instantaneous Description

An instantaneous description of $T$ is a finite string over $\Gamma \cup Q$ of the form:

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

where:

  • $m, n \in \set {0, 1, 2, \dotsc}$
  • $q \in Q$
  • $X_i, Y, Z_j \in \Gamma$ for all $1 \le i \le m$ and $1 \le j \le n$
  • If $m \ge 1$, then $X_m \ne B$
  • If $n \ge 1$, then $Z_n \ne B$


Move

Let:

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

be an instantaneous description of $T$.

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

Then, $T$ is said to move from instantaneous description $A$ to the unique instantaneous description $A'$ defined as follows:

If $d = L$, then:
$A' = X_m X_{m - 1} \dotsm X_2 q X_1 Y' Z_1 Z_2 \dotsm Z_{n - 1} Z_n$
If $d = R$, then:
$A' = X_m X_{m - 1} \dotsm X_2 X_1 Y' q Z_1 Z_2 \dotsm Z_{n - 1} Z_n$


There are certain special cases that occur in the above when $m$ or $n$ is $0$, to preserve the form of an instantaneous description.

If either $m = 0$ and $d = L$, or $n = 0$ and $d = R$, the missing $X_1$ or $Z_1$ is replaced with $B$ in $A'$.

On the other hand, if $Y' = B$, and either $m = 0$ and $d = R$, or $n = 0$ and $d = L$, then $Y'$ is omitted from $A'$.


If $T$ moves from $A$ to $A'$, this fact is denoted:

$A \vdash_T A'$


Furthermore, if there exists a finite sequence of instantaneous descriptions $\sequence {A_0, A_1, \dots, A_N}$ such that:

$A_0 \vdash_T A_1 \vdash_T \dotso \vdash_T A_N$

then $T$ is said to eventually move from $A_0$ to $A_N$, and this fact is denoted:

$A_0 \vdash_T^* A_N$


Halting

Let:

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

be an instantaneous description of $T$.

Then, $A$ is said to be halting if and only if $\delta$ is undefined at $\tuple {q, Y}$.


Furthermore, let $C$ be another instantaneous description of $T$.

If $T$ eventually moves from $C$ to $A$, then $T$ is said to eventually halt from $C$ at $A$.


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$.


Examples

Natural Number Addition

Let $\TT$ be a Turing machine whose task is to implement addition on the non-zero natural numbers.


Let $a, b \in \N_{>0}$ be expressed in unary notation:

\(\ds a\) \(=\) \(\ds \underbrace {111 \ldots 1}_{\text {$a$ times} }\)
\(\ds b\) \(=\) \(\ds \underbrace {111 \ldots 1}_{\text {$b$ times} }\)

$a$ and $b$ are to be presented to $\TT$ on a tape in the form:

$0000 \underbrace {111 \ldots 1}_{\text {$a$ times} } 0 \underbrace {111 \ldots 1}_{\text {$b$ times} } 000$

That is, $a$ and $b$ are presented on the tape with one $0$ between them.


The program of $\TT$ is of the form:

\(\ds \) \(\) \(\ds \tuple {1, 0, 0, \mathrm R, 1}\)
\(\ds \) \(\) \(\ds \tuple {1, 1, 0, \mathrm R, 2}\)
\(\ds \) \(\) \(\ds \tuple {2, 0, 1, \mathrm R, \mathrm H}\)
\(\ds \) \(\) \(\ds \tuple {2, 1, 1, \mathrm R, 2}\)

The elements of each tuple are interpreted as follows:

\((1)\)   $:$   the state of $\TT$ for which this instruction applies      
\((2)\)   $:$   the symbol on the tape that is currently being read by $\TT$      
\((3)\)   $:$   the symbol which is to replace that which is currently being read by $\TT$      
\((4)\)   $:$   the direction in which to move $\TT$ over the tape: $\mathrm R$ for right, $\mathrm L$ for left      
\((5)\)   $:$   the state of $\TT$ after this instruction has been performed      

$\TT$ starts in state $1$.


Also known as

A Turing machine as defined here 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=747012"