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

Link to original

Halting Problem

Definition

The halting problem $A_{TM}$ is the problem of determining, given a Turing Machine $M$ and input $w$, whether $M$ halts on $w$. $A_{TM}=\{⟨M,w⟩\mid M\text{ is a TM and }M\text{ halts on }w\}$

Undecidability

$A_{TM}$ is Recursively Enumerable Language but not Decidable. This proves strictly that $\text{Decidable}⊊\text{RE}$.

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.