Church-Turing Thesis

Mort Yao

Turing machine (TM). A Turing machine \(M\) is a 7-tuple \((Q, \Sigma, \Gamma, \delta, q_0, q_\text{accept}, q_\text{reject})\), where

\(Q\) is a finite set called the states,
\(\Sigma\) is a finite set called the input alphabet, (the blank symbol \(\sqcup \notin \Sigma\))
\(\Gamma\) is a finite set called the tape alphabet, (\(\sqcup \in \Gamma\) and \(\Sigma \subseteq \Gamma\))
\(\delta : Q' \times \Gamma \to Q \times \Gamma \times \{\text{L}, \text{R}\}\) is the transition function, (where \(Q' = Q-\{q_\text{accept},q_\text{reject}\}\))
\(q_0 \in Q\) is the start state,
\(q_\text{accept}\) is the accept state,
\(q_\text{reject}\) is the reject state. (\(q_\text{reject} \neq q_\text{accept}\))

A Turing machine configuration \(C\) is written as \(u\ q\ v\), where

\(u \in \Gamma^*\) is the sequence of characters before the tape head,
\(q \in Q\) is the current state,
\(v \in \Gamma^*\) is the character at the tape head and all following characters up to the last non-blank character.

Suppose that we have \(a, b, c \in \Gamma\), \(u, v \in \Gamma^*\), and \(q_i, q_j \in Q\), we say that configuration \(C_1\) yields configuration \(C_2\) if a single transition of the Turing machine converts \(C_1\) to \(C_2\). Formally:

(Leftward move) \(u a\ q_i\ b v\) yields \(u\ q_j\ a c v\), if \(\delta(q_i, b) = (q_j, c, \text{L})\);
- Specially, \(q_i\ b v\) yields \(q_j\ c v\);
(Rightward move) \(u a\ q_i\ b v\) yields \(u a c\ q_j\ v\), if \(\delta(q_i, b) = (q_j, c, \text{R})\).
- Specially, \(u a\ q_i\) yields \(u a c\ q_j\), if \(\delta(q_i, \sqcup) = (q_j, c, \text{R})\).

The start configuration of a Turing machine \(M\) on input \(w\) is the configuration \(q_0\ w\). In an accepting configuration, the state of the configuration is \(q_\text{accept}\). In a rejecting configuration, the state of the configuration is \(q_\text{reject}\). Accepting and rejecting configurations are called halting configurations and cannot yield further configurations.

We say that the Turing machine \(M = (Q, \Sigma, \Gamma, \delta, q_0, q_\text{accept}, q_\text{reject})\) accepts a string \(w\) if there exists a sequence of configurations \(C_1, \dots, C_k\), where

\(C_1\) is the start configuration of \(M\) on input \(w\),
Each \(C_i\) yields \(C_{i+1}\),
\(C_k\) is an accepting configuration.

On the contrary, if \(C_k\) is a rejecting configuration, we say that the Turing machine \(M\) rejects the string \(w\).

\(L\) is the language of Turing machine \(M\), denoted as \(\mathcal{L}(M) = L\), if and only if \[L = \{ w\ |\ w \text{ is a string accepted by } M \}\] We also say that language \(L\) is recognized by Turing machine \(M\).

Turing recognizability. A language \(L\) is Turing-recognizable if and only if there exists a Turing machine \(M\) that recognizes \(L\). A Turing-recognizable language is also called a recursively enumerable language.

Turing decidability. A language \(L\) is Turing-decidable (or simply decidable) if and only if there exists a Turing machine \(M\) that accepts every \(w \in L\) and rejects every \(w \notin L\). A decidable language is also called a recursive language.

Clearly, every decidable language is Turing-recognizable; however, not every Turing-recognizable language is decidable, i.e., for some language \(L\), there exists a string \(w\) that can neither be accepted (\(w \in L\)) nor rejected (\(w \notin L\)) by any Turing machine.

Theorem 1. (Closure properties) The class of Turing-recognizable languages is closed under union, intersection, concatenation, Kleene star and homomorphism.

Theorem 2. (Closure properties) The class of decidable languages is closed under union, intersection, complementation, concatenation and Kleene star.

Proof.

(1) Closure under union.

For any two decidable languages \(L_1\) and \(L_2\), let \(M_1\) and \(M_2\) be the TMs that decide them. We construct a TM \(M'\) that decides the union of \(L_1\) and \(L_2\):

\(M' =\) “On input \(w\):

Run \(M_1\) on \(w\). If it accepts, accept.

Run \(M_2\) on \(w\). If it accepts, accept. Otherwise, reject.’’

\(M'\) accepts \(w\) if and only if either \(M_1\) or \(M_2\) accepts it. If both reject, \(M'\) rejects.

(2) Closure under intersection.

For any two decidable languages \(L_1\) and \(L_2\), let \(M_1\) and \(M_2\) be the TMs that decide them. We construct a TM \(M'\) that decides the intersection of \(L_1\) and \(L_2\):

\(M' =\) “On input \(w\):

Run \(M_1\) on \(w\). If it rejects, reject.

Run \(M_2\) on \(w\). If it accepts, accept. Otherwise, reject.’’

\(M'\) accepts \(w\) if and only if both \(M_1\) and \(M_2\) accept it. If either rejects, \(M'\) rejects.

(3) Closure under complementation.

For any decidable language \(L\), let \(M\) be the TM that decides it. We construct a TM \(M'\) that decides the complement of \(L\):

\(M' =\) “On input \(w\):

Run \(M\) on \(w\). If it accepts, reject. Otherwise, accept.’’

\(M'\) accepts \(w\) if and only if it is rejected by some TM \(M\). Otherwise, \(M'\) rejects.

(4) Closure under concatenation.

For any two decidable languages \(L_1\) and \(L_2\), let \(M_1\) and \(M_2\) be the TMs that decide them. We construct an NTM \(M'\) that decides the concatenation of \(L_1\) and \(L_2\):

\(M' =\) “On input \(w\):

For each \(w_1, w_2\) such that \(w = w_1w_2\):

Run \(M_1\) on \(w_1\).

Run \(M_2\) on \(w_2\). If for some \(w_1\) and \(w_2\), both are accepted, accept.

If not accepted, reject.’’

\(M'\) accepts \(w\) if and only if for some \(w_1\) and \(w_2\) such that \(w = w_1w_2\), both \(w_1\) and \(w_2\) are accepted by some TMs. Since there are finitely many ways of splitting \(w = w_1w_2\), \(M'\) is guaranteed to halt.

(5) Closure under Kleene star.

For any decidable language \(L\), let \(M\) be the TM that decides it. We construct an NTM \(M'\) that decides the Kleene star of \(L\):

\(M' =\) “On input \(w\):

For each \(w_1, \dots, w_n\) such that \(w = w_1 \dots w_n\):

Run \(M\) on each \(w_i\) (for \(i = 1, \dots, n\)). If \(M\) accepts every \(w_i\), accept.

If not accepted, reject.’’

\(M'\) accepts \(w\) if and only if for some \(w_1, \dots, w_n\) such that \(w = w_1 \dots w_n\), every \(w_i\) is accepted by some TM \(M\). Since there are finitely many ways of splitting \(w = w_1 \dots w_n\), \(M'\) is guaranteed to halt.

■

Church-Turing thesis. Everything that can be effectively computed can be computed using a Turing machine (or the lambda calculus).

Equivalent models of computation:

(Single-tape, deterministic) Turing machine;
Multi-tape Turing machine;
Nondeterministic Turing machine;
Enumerator;
Abstract rewriting system;
Lambda calculus;
etc.