2 Turing Machine

A Turing Machine $M$ is $(Q, Σ, δ, q_{0})$

$Q (∋ q_{i}), h \notin Q$	Set of states, $h$ halting state
$Σ (∋ σ, σ^{'}, \hdots)$	Set of symbols
$q_{0} \in Q$	Initial state
$δ \subseteq (Q \times Σ) \times (Q \cup {h} \times Σ \times {L, R, -})$	is the transition function
if $(q, ▹, q^{'}, σ, D) \in δ$	then $σ = ▹, D = R$

$Σ^{*}$ is the free monoid generated from $Σ$ . $" \cdot "$ is the associative string concatenation operator. $ϵ$ is the empty string and identity element.

2.1 Configuration

A configuration $C$ of a TM $M$ is a quadruple: $(q, u, σ, v) \in (Q \cup {h}) \times Σ^{*} \times Σ \times Σ^{F})$ where $Σ^{F} = Σ^{*} \cdot (Σ ∖ {#}) \cup {ϵ}$ .

$σ$ is the currently selected symbol under the head of the machine. Short notation is $(q, u \underset{―}{σ} v)$ or $(q, w)$ when position is not needed.

2.2 Computations

A computation is a finite succession of computation steps

$(q, w) \to (q^{'}, w^{'})$	Computation step
$(q_{0}, w) \to^{*} (q^{'}, w^{'})$	Reflexive and transitive closure of comp. steps.
$(q_{0}, w) \to_{M}^{n} (q^{'}, w^{'})$	Machine $M$ computes $w^{'}$ in $n$ steps.
$↓, ↑$	Converges and diverges

2.3 T(uring)-Computability

Let $Σ, Σ_{0}, Σ_{1}$ be alphabets, let $#, ▹ \notin Σ_{0} \cup Σ_{1}$ and $Σ_{0} \cup Σ_{1} \subset Σ$ .

Let $f$ be a function $f : Σ_{0}^{*} \to Σ_{1}^{*}$ .

f

is turing computable by a machine

M

\Leftrightarrow

\forall w \in Σ_{0}^{*} : f (w) = z \Leftrightarrow (q_{0}, \underset{―}{▹} w) \to_{M}^{*} (h, ▹ z \underset{―}{#})

sectionProblems and Functions

2.4 Poly reduction

$L_{1} \leq_{P} L_{2}$ Then exsit $f \in O (n) \mapsto | f (w) | = n^{k}$ for some k

2.5 Total Function

$f : A \to B$ , subset of $A \times B$ is total $\Leftrightarrow$

$\forall a \in A \exists b \in B : (a, b) \in f$	$f$ is defined everywhere
$(a, b), (a, c) \in f \Rightarrow b = c$	uniqueness

2.6 Partial Function

$f : A \to B$ , subset of $A \times B$ is a partial function $\Leftrightarrow$

$(a, b), (a, c) \in f \Rightarrow b = c$	uniqueness
$\exists$ at least a $b \in B : f (a) = b$	not required to be defined everywhere

Theorem

Computable functions are $# (N)$ . Total computable functions are $# (N)$ . There exists functions that are not computable.

Proof ▼

Computable functions can be given a Gödel numbering. Therefore there exists a 1-1 mapping with natural numbers. All the possible total functions ${f : N \to N}$ are $2^{# (N)}$ .

Theorem

Padding Lemma: every computable function $φ_{i}$ has $# (N)$ indexes. $\forall i . \exists A_{i}$ infinite set of indexes such that $\forall y \in A_{i} . φ_{y} = φ_{i}$

Proof ▼

If a program $P_{j}$ in WHILE computes $φ_{i}$ , one can build $# (N)$ other programs that compute the same thing, semantically equal to $φ_{i}$ by just adding a skip command at the end of the program. The new program’s index will change because an effective numbering depends only on the syntactic description of the program.

Theorem

The class of Primitive Recursive functions (and extensions) does not contain all the effectively computable functions:

Proof ▼

reductio ad absurdum

1: Encode and enumerate p.r. functions	$f_{0}, \hdots, f_{n}$ . There are $N$
2: Define diagonal func. $g (x) = f_{x} (x) + 1$	Intuitively computable
3: $\forall n . g (n) \neq f_{n} (n) \Rightarrow \forall n . g \neq f_{n}$	$g$ doesn’t appear in list

Implies there is no formalism for expressing only and all total functions.

Recursion Axiom

Let $h$ be a p.r. func. in $k + 1$ variables, $g$ be a p.r. func in $k - 1$ variables. The function $f$ in $k$ variables defined as follow is then p.r.

f = {\begin{matrix} f (0, x_{2}, \hdots, x_{k}) & = & g (x_{2}, \hdots, x_{k}) & final step \\ f (x_{1} + 1, \hdots, x_{k}) & = & h (x_{1}, f (x_{1}, \hdots, x_{k}), x_{2}, \hdots, x_{k}) & iteration \end{matrix}

This represents a FOR loop. $x_{1}$ , the first variable of $f$ is the decrementing counter. $g$ is the final step. $h$ represents loop steps. This is guaranteed to terminate. One can define basic maths primitives with p.r. functions.

Theorem

Enumeration: $\exists z . \forall i, x . φ_{z} (i, x) = φ_{i} (x)$

Proof ▼

Guarantees that a formalism that expresses all computable function has an universal algorithm. Therefore there exists an Universal Turing Machine. $φ_{z} (i, x) = U (μ y . T (i, x, y)) = φ_{i} (x)$ □