Turing Machine

Definition

A Turing machine is a 7-tuple $(Q,\Sigma ,\Gamma ,\delta ,q_0,q_{accept},q_{reject})$ where:

1. $Q$ is a finite set of states.
2. $\Sigma$ is a finite input alphabet.
3. $q_0\in Q$ is the start state.
4. $\Gamma$ is the tape alphabet, where $\Sigma \subset \Gamma$ and the blank symbol $\bigsqcup \in \Gamma \setminus \Sigma$.
5. $\delta :Q\times \Gamma \to Q\times \Gamma \times \{L,R\}$ is the transition function (state, write, move).
6. $q_a,q_r\in Q$ are distinct accept/reject halting states.

Results

Statement

The Church-Turing thesis is the hypothesis that the informal notion of “effectively calculable” functions coincides exactly with the functions computable by a Turing machines.

Link to original

Halting Problem

Idea

The halting problem is a decision procedure for deciding whether a Turing machines $M$ halts on an input string $w$. It was proven by Turing that such a problem is undecidable.

Definition

$\mathbf{Halt}:TM(\Sigma )\times {\Sigma }^{\ast }\to \mathbb{B}$ be defined as $P(M,w)=\top$ iff $M$ terminates on input $w$, where $TM(\Sigma )$ is the set of Turing machines on an input language $\Sigma$.

Undecidability

$H$ is recursively enumerable but not decidable.
The proof essentially goes:

1. Fix $e:TM(\Sigma )\times {\Sigma }^{\ast }\to {\Sigma }^{\ast }$ to be an injective computable encoding.
2. Suppose for a contradiction that you have a decider $H$ for the language $\mathbf{Halt}\circ e$.
3. Construct a TM $M:TM(\Sigma )$ that given an input machine $N$ runs $H$ on $⟨N,N⟩$.
4. If $H$ returns $\top$ then loop, otherwise halt (it doesn’t matter what is returned).
5. Now run $M$ on $M$. This terminates iff $H⟨M,M⟩=\perp$ iff $M$ doesn’t terminate.
6. Contradiction. Hence no such deciding TM can exist.
   This proves that the set of decidable problems is a strict subset of the recursively enumerable languages.

Link to original

Language Class

TMs recognize Recursively Enumerable Languages. A language is Decidable iff it is decided by a TM that halts on all inputs.