Turing Machines, Configurations, and Computation

A deterministic one-tape Turing machine with designated accept and reject states is a tuple $M=(Q,\mathrm{\Sigma },\mathrm{\Gamma },\bigsqcup ,q_0,q_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{r}\mathrm{e}\mathrm{j}},\delta )$ such that:

• $Q$ is a finite set of states.
• $\mathrm{\Sigma }$ is a finite input alphabet.
• $\mathrm{\Gamma }$ is a finite tape alphabet with $\mathrm{\Sigma }\subseteq \mathrm{\Gamma }\setminus \{\bigsqcup \}$.
• $\bigsqcup \in \mathrm{\Gamma }$ is the blank symbol.
• $q_0,q_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{r}\mathrm{e}\mathrm{j}}\in Q$ are pairwise distinct.
• $\delta$ is a function $\delta :(Q\setminus \{q_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{r}\mathrm{e}\mathrm{j}}\})\times \mathrm{\Gamma }\to Q\times \mathrm{\Gamma }\times \{L,R\}\mathrm{.}$

Thus whenever the machine is in a nonhalting state $q$ and scans a symbol $a\in \mathrm{\Gamma }$, the value $\delta (q,a)=(q^{\mathrm{\prime }},b,D)$ specifies exactly one next state $q^{\mathrm{\prime }}$, exactly one symbol $b$ to write in the currently scanned cell, and exactly one head move $D\in \{L,R\}$.

The intended tape is right-infinite and indexed by the natural numbers (Computation alphabets, words, the empty word, and ${\mathrm{\Sigma }}^{\ast }$, A function is a relation $f$ with $(a,b)\in f$ and $(a,c)\in f$ implying $b=c$; $f:A\to B$, the value $f(a)$, domain and codomain); the tape contents, configurations, and one-step dynamics are fixed in the next items.

• The transition function is total on the nonhalting state-symbol pairs. The machine halts by entering one of the distinguished states $q_{\mathrm{a}\mathrm{c}\mathrm{c}}$ or $q_{\mathrm{r}\mathrm{e}\mathrm{j}}$, not by leaving $\delta$ undefined.

• This item fixes only the base deterministic one-tape model. Multitape and nondeterministic variants are introduced later on the same page.

Fix a deterministic one-tape Turing machine $M=(Q,\mathrm{\Sigma },\mathrm{\Gamma },\bigsqcup ,q_0,q_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{r}\mathrm{e}\mathrm{j}},\delta )$. A tape content for $M$ is a function $t:\mathbb{N}\to \mathrm{\Gamma }$ (A function is a relation $f$ with $(a,b)\in f$ and $(a,c)\in f$ implying $b=c$; $f:A\to B$, the value $f(a)$, domain and codomain, The natural numbers $\mathbb{N}$ (von Neumann)) such that the support $\mathrm{supp}(t):=\{n\in \mathbb{N}:t(n)\mathrm{\ne }\bigsqcup \}$ is finite.

Thus the tape is indexed by the natural numbers, extends infinitely to the right, and is blank except at finitely many cells. If the head is instructed to move left from cell $0$, it remains at cell $0$.

For an input word $w=a_0{a}_1\cdots a_{m-1}\in {\mathrm{\Sigma }}^{\ast }$, the initial tape $t_w:\mathbb{N}\to \mathrm{\Gamma }$ is defined by $t_w(i):=\{\begin{array}{ll}{a}_i,& 0\le i<m,\\ \bigsqcup ,& i\ge m\mathrm{.}\end{array}$ Its support is contained in $\{0,\dots ,m-1\}$ and is therefore finite.

• This finite-support convention is a clean way to formalize the usual picture "the tape is blank except on a finite used segment."

• The head position is not part of the tape content; it is a separate natural number in the configuration definition.

Fix a deterministic one-tape Turing machine $M=(Q,\mathrm{\Sigma },\mathrm{\Gamma },\bigsqcup ,q_0,q_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{r}\mathrm{e}\mathrm{j}},\delta )$. A configuration of $M$ is a triple $C=(q,h,t)$ where $q\in Q$ is the current state, $h\in \mathbb{N}$ is the current head position, and $t:\mathbb{N}\to \mathrm{\Gamma }$ is a tape content in the sense of Right-infinite tapes as finite-support functions.

The symbol currently scanned in $C$ is $t(h)$. The configuration is nonhalting when $q\mathrm{\notin }\{q_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{r}\mathrm{e}\mathrm{j}}\}$.

For later encoding arguments it is convenient to write a configuration as a finite word over the alphabet $Q\cup \mathrm{\Gamma }$: if $r=\max (\{h\}\cup \mathrm{supp}(t))$, and $a_i:=t(i)$ for $0\le i\le r$, then the associated configuration word is $a_0{a}_1\cdots a_{h-1}q{a}_h\cdots a_r\mathrm{.}$ The state symbol is inserted immediately before the scanned tape symbol, and the word is long enough to include the head position even when the scanned cell is blank.

• This is the modern full-configuration convention: state, head position, and whole finite tape data are all part of the object.

• Turing's original narrower word "configuration" for the pair "state plus scanned symbol" is not the convention used on this page.

Fix a deterministic one-tape Turing machine $M=(Q,\mathrm{\Sigma },\mathrm{\Gamma },\bigsqcup ,q_0,q_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{r}\mathrm{e}\mathrm{j}},\delta )$. Let $C=(q,h,t)$ and $C^{\mathrm{\prime }}=(q^{\mathrm{\prime }},h^{\mathrm{\prime }},t^{\mathrm{\prime }})$ be configurations of $M$.

We say that $C^{\mathrm{\prime }}$ follows $C$ in one step, and write $C{⊢}_M{C}^{\mathrm{\prime }},$ when $q\mathrm{\notin }\{q_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{r}\mathrm{e}\mathrm{j}}\}$ and, writing $\delta (q,t(h))=(p,b,D),$ one has:

• $q^{\mathrm{\prime }}=p$,
• $t^{\mathrm{\prime }}(h)=b$,
• $t^{\mathrm{\prime }}(i)=t(i)$ for every $i\mathrm{\ne }h$,
• if $D=R$, then $h^{\mathrm{\prime }}=h+1$,
• if $D=L$ and $h>0$, then $h^{\mathrm{\prime }}=h-1$,
• if $D=L$ and $h=0$, then $h^{\mathrm{\prime }}=0$.

So one step changes only the scanned tape cell, updates the state, and moves the head one cell right or one cell left, except that the left boundary clamps the head at cell $0$.

• Because $t^{\mathrm{\prime }}$ differs from $t$ at at most one position, it is again a finite-support tape content.

• There is no one-step successor from an accepting or rejecting configuration.

Let $M$ be a deterministic one-tape Turing machine. Every nonhalting configuration of $M$ has exactly one one-step successor.

Fix a deterministic one-tape Turing machine $M=(Q,\mathrm{\Sigma },\mathrm{\Gamma },\bigsqcup ,q_0,q_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{r}\mathrm{e}\mathrm{j}},\delta )$ and an input word $w\in {\mathrm{\Sigma }}^{\ast }$.

The initial configuration of $M$ on input $w$ is $I_M(w):=(q_0,0,t_w),$ where $t_w$ is the initial tape from Right-infinite tapes as finite-support functions.

A configuration $C=(q,h,t)$ of $M$ is:

• accepting if $q=q_{\mathrm{a}\mathrm{c}\mathrm{c}}$,
• rejecting if $q=q_{\mathrm{r}\mathrm{e}\mathrm{j}}$,
• halting if it is accepting or rejecting.

Thus the machine starts in state $q_0$, scans the leftmost input cell, and halts exactly when it enters one of the two designated halting states.

• If $w=\epsilon$, then the initial tape is blank everywhere and the head is still at cell $0$.

• Accepting and rejecting are properties of configurations, not of words. The same input may lead different machines to different outcomes.

Fix a deterministic one-tape Turing machine $M=(Q,\mathrm{\Sigma },\mathrm{\Gamma },\bigsqcup ,q_0,q_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{r}\mathrm{e}\mathrm{j}},\delta )$ and an input word $w\in {\mathrm{\Sigma }}^{\ast }$.

Configurations are triples $(q,h,t)$ as in Configurations of a deterministic one-tape Turing machine. Write $I_M(w)=(q_0,0,t_w)$, where $t_w$ is the input word followed by blanks, the initial tape of Right-infinite tapes as finite-support functions. For the empty word it is blank everywhere. A configuration is accepting when its state is $q_{\mathrm{a}\mathrm{c}\mathrm{c}}$, rejecting when its state is $q_{\mathrm{r}\mathrm{e}\mathrm{j}}$, and halting when either condition holds. The two halting states are distinct. The relation ${⊢}_M$ is the one-step relation of The one-step configuration relation.

A finite computation history of $M$ on input $w$ is a finite list of configurations, meaning a function on $\{0,\dots ,n\}$ with values in the configuration set (A function is a relation $f$ with $(a,b)\in f$ and $(a,c)\in f$ implying $b=c$; $f:A\to B$, the value $f(a)$, domain and codomain), written $C_0,C_1,\dots ,C_n$ such that $C_0=I_M(w)$ and $C_i{⊢}_M{C}_{i+1}(0\le i<n)\mathrm{.}$

Such a history is:

• accepting if $C_n$ is an accepting configuration,
• rejecting if $C_n$ is a rejecting configuration,
• halting if it is accepting or rejecting.

We say that $M$ halts on $w$ if there exists a halting computation history of $M$ on $w$.

We say that $M$ diverges on $w$ if there is no halting computation history of $M$ on $w$.

For a halting configuration $C=(q,h,t)$ and a word $u=a_0\cdots a_{m-1}$ over $\mathrm{\Gamma }\setminus \{\bigsqcup \}$, we say that $C$ outputs $u$ when $t(i)=\{\begin{array}{ll}{a}_i,& 0\le i<m,\\ \bigsqcup ,& i\ge m\mathrm{.}\end{array}$ So the tape contains exactly $u$ followed by blanks.

• On a deterministic machine there is at most one possible next configuration from a nonhalting configuration, but the definition of divergence here is simply "no halting computation history exists."

• The output convention is intentionally strict: the final nonblank tape segment must be exactly the displayed word, with no later nonblank cells.

Let $M$ be a deterministic one-tape Turing machine with input alphabet $\mathrm{\Sigma }$, and let $L\subseteq {\mathrm{\Sigma }}^{\ast }$ be a language (Languages over an alphabet).

We say that $M$ recognizes $L$ if for every input word $w\in {\mathrm{\Sigma }}^{\ast }$, $w\in L⟺M\text{ has an accepting computation on }w\mathrm{.}$

We say that $M$ decides $L$ if $M$ recognizes $L$ and halts on every input $w\in {\mathrm{\Sigma }}^{\ast }$.

Equivalently, $M$ decides $L$ exactly when every input has either an accepting or rejecting computation history and $w\in L⟺M\text{ accepts }w,w\mathrm{\notin }L⟺M\text{ rejects }w\mathrm{.}$

• A recognizer may diverge on words not in the language. Total halting is the extra condition that upgrades recognition to decision.

• The ambient alphabet $\mathrm{\Sigma }$ matters: recognition and decidability are always statements about a subset of one fixed ${\mathrm{\Sigma }}^{\ast }$.

Let $X$ and $Y$ be sets, let $e_X:X\to \{0,1{\}}^{\ast },e_Y:Y\to \{0,1{\}}^{\ast }$ be effective binary encodings in the sense of Effective binary encodings and total decoders, let $M=(Q,\{0,1\},\mathrm{\Gamma },\bigsqcup ,q_0,q_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{r}\mathrm{e}\mathrm{j}},\delta )$ be a deterministic one-tape Turing machine, and let $f:D\to Y$ be a function with domain $D\subseteq X$.

The machine $M$ computes the partial function $f$ under the fixed encodings $e_X,e_Y$ if:

• for every $x\in D$, the computation of $M$ on input $e_X(x)$ halts and its final configuration outputs the binary word $e_Y(f(x))$, and
• for every $x\in X\setminus D$, the computation of $M$ on input $e_X(x)$ diverges.

Thus the machine's input and output are ordinary finite binary words, while the mathematical function lives on the underlying sets $X$ and $Y$ through the chosen encodings.

• This definition intentionally separates the machine from the represented function. Changing the encoding can change which partial function a fixed machine computes.

• Nothing in the definition requires any particular behaviour on malformed binary strings outside the image of $e_X$.

Fix finite alphabets $\mathrm{\Sigma }\subseteq \mathrm{\Gamma }\setminus \{\bigsqcup \}$ with $\bigsqcup \in \mathrm{\Gamma }$, and a finite state set $Q$ with distinct states $q_0,q_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{r}\mathrm{e}\mathrm{j}}\in Q$.

For an integer $k\ge 1$, a deterministic $k$-tape Turing machine has the same finite control data as the one-tape model, but carries $k$ right-infinite tapes and $k$ head positions. Its transition function has the form ${\delta }_k:(Q\setminus \{q_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{r}\mathrm{e}\mathrm{j}}\})\times {\mathrm{\Gamma }}^k\to Q\times {\mathrm{\Gamma }}^k\times \{L,R{\}}^k\mathrm{.}$ So one step reads one symbol from each tape, writes one symbol on each tape, and moves each head left or right.

A nondeterministic one-tape Turing machine has the same data $(Q,\mathrm{\Sigma },\mathrm{\Gamma },\bigsqcup ,q_0,q_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{r}\mathrm{e}\mathrm{j}})$ as the deterministic model, but replaces the transition function by a finite-valued transition map $\mathrm{\Delta }:(Q\setminus \{q_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{r}\mathrm{e}\mathrm{j}}\})\times \mathrm{\Gamma }\to {\mathcal{P}}_{\mathrm{f}\mathrm{i}\mathrm{n}}(Q\times \mathrm{\Gamma }\times \{L,R\}),$ where each $\mathrm{\Delta }(q,a)$ is a finite set of allowed next instructions.

• This page only fixes the variant models themselves. The equivalence and simulation theorems relating them to the basic one-tape model come later.

• In the nondeterministic case, more than one next instruction may be available from the same state-symbol pair; acceptance is therefore defined by existence of an accepting branch.

Fix a nondeterministic one-tape Turing machine $N=(Q,\mathrm{\Sigma },\mathrm{\Gamma },\bigsqcup ,q_0,q_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{r}\mathrm{e}\mathrm{j}},\mathrm{\Delta })$ and an input word $w\in {\mathrm{\Sigma }}^{\ast }$.

A configuration of $N$ is a triple $(q,h,t)$ with $q\in Q$, head position $h\in \mathbb{N}$, and finite-support tape content $t:\mathbb{N}\to \mathrm{\Gamma }$, just as in Configurations of a deterministic one-tape Turing machine. It is accepting when $q=q_{\mathrm{a}\mathrm{c}\mathrm{c}}$ and rejecting when $q=q_{\mathrm{r}\mathrm{e}\mathrm{j}}$. The initial configuration is $(q_0,0,t_w)$, where $t_w$ is the input word followed by blanks as in Right-infinite tapes as finite-support functions, including the all-blank tape for empty input. These definitions use only the shared state/alphabet data of the deterministic and nondeterministic models.

For configurations $C=(q,h,t)$ and $C^{\mathrm{\prime }}=(q^{\mathrm{\prime }},h^{\mathrm{\prime }},t^{\mathrm{\prime }})$ of $N$, write $C{⊢}_N{C}^{\mathrm{\prime }}$ when $q\mathrm{\notin }\{q_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{r}\mathrm{e}\mathrm{j}}\}$ and there exists an allowed instruction $(p,b,D)\in \mathrm{\Delta }(q,t(h))$ such that $C^{\mathrm{\prime }}$ is obtained from $C$ by the same local rewrite and head-move recipe used in The one-step configuration relation, with $q^{\mathrm{\prime }}=p$.

An accepting computation of $N$ on input $w$ is a finite list of configurations, that is, a function on $\{0,\dots ,n\}$ with configuration values (A function is a relation $f$ with $(a,b)\in f$ and $(a,c)\in f$ implying $b=c$; $f:A\to B$, the value $f(a)$, domain and codomain), written $C_0,C_1,\dots ,C_n$ such that $C_0=(q_0,0,t_w)$, where $t_w$ is the input tape defined in the same way as for deterministic machines, each $C_i{⊢}_N{C}_{i+1}$ for $0\le i<n$, and $C_n$ is accepting.

We say that $N$ accepts $w$ if such an accepting computation exists.

• Nondeterministic acceptance is existential: one accepting branch is enough.

• Other branches may reject, may halt differently, or may continue forever; no global halting requirement is part of acceptance itself.

Fix a deterministic one-tape Turing machine $M$ and an input word $w$ for $M$. Then one can choose a binary encoding of configurations of $M$ and a binary encoding of finite tuples of such codes so that the set $H_{M,w}$ of encoded accepting computation histories of $M$ on input $w$ is a decidable language over $\{0,1\}$.

Let $N$ be either a deterministic one-tape Turing machine or a nondeterministic one-tape Turing machine, and fix an input word $w$.

Write $C{⇝}_N{C}^{\mathrm{\prime }}$ when $C^{\mathrm{\prime }}$ follows $C$ by one legal step of $N$: in the deterministic case this means $C{⊢}_N{C}^{\mathrm{\prime }}$ in the sense of The one-step configuration relation, and in the nondeterministic case it means that one allowed instruction of $N$ changes $C$ to $C^{\mathrm{\prime }}$ by the same local rewrite and head-move rule.

The configuration graph of $N$ on $w$ is the directed graph $G_N(w)=(V,A)$ whose vertex set $V$ is the set of all configurations reachable from the initial configuration $(q_0,0,t_w)$ by finitely many legal steps, where $t_w$ is the input tape for $w$, and whose arc set $A\subseteq V\times V$ consists of the ordered pairs $(C,C^{\mathrm{\prime }})$ such that $C{⇝}_N{C}^{\mathrm{\prime }}\mathrm{.}$

This uses the same ordered-pair arc convention as a digraph in Multigraphs, loops and directed graphs as variants distinct from the default finite simple graph, but no finiteness claim is made here: the configuration graph may be infinite.

An accepting vertex is an accepting configuration of $N$.

• For a deterministic machine every nonhalting vertex has out-degree $1$, while for a nondeterministic machine it may have several outgoing arcs.

• The graph need not be acyclic. Looping computations and revisited configurations are part of the present scope.

Let $N$ be either a deterministic one-tape Turing machine or a nondeterministic one-tape Turing machine, and fix an input word $w$. Then $N$ accepts $w$ if and only if, in the configuration graph $G_N(w)$, some accepting configuration is reachable from the initial configuration.

False claim: whenever a deterministic Turing machine rejects an input, it diverges on that input.

False claim: a nondeterministic Turing machine accepts an input only when every computation branch on that input halts.