Machine Models and Basic Computability Theory

Overview

Covers Post machines, Turing machines, Turing's analysis of human computation, formal definitions, and typical features of computation models.
Introduces elementary recursion theory: unsolvable problems, the Halting problem, recursively enumerable (r.e.) and recursive sets, the universal language, and the Chomsky hierarchy.

Post Machine (1936)

Primitive acts (worker operates on a one-dimensional tape of boxes):
- (a) Marking the box he is in (assumed empty).
- (b) Erasing the mark in the box he is in (assumed marked).
- (c) Moving to the box on his right.
- (d) Moving to the box on his left.
- (e) Determining whether the box he is in is marked or not.
Directions (finite list of instructions numbered $1, 2, \dots, n$):
- Perform operation $O_i \in \{(a), (b), (c), (d)\}$, then follow direction $j_i$.
- Perform operation (e) and, according to yes/no, follow direction $j_i'$ or $j_i''$.
- Stop.
Exercise: Construct a Post machine that adds one to a natural number in unary representation.

Paper tape: Divided into squares (one-dimensional).
Symbols: Finite number of symbols allowed.
Behavior: At any moment determined by observed symbols and the computer's "state of mind".
Bounds:
- Bound $B$ on the number of symbols/squares observable at any moment.
- Finite number of "states of mind".
Simple operations:
- (a) Change a single symbol on one of the $B$ observed squares.
- (b) Change one observed square to another at most $L$ squares away.
Conclusion: These simple operations are sufficient for any computation of a number, and they closely correspond to Turing machine operations.

Definition: A Turing machine is a tuple: $$ M = \langle Q, \Sigma, \Gamma, \delta, q_0, b, F \rangle $$ where:
- $Q$: finite set of states.
- $\Sigma$: input alphabet.
- $\Gamma$: finite tape alphabet, with $\Gamma \supseteq \Sigma \cup \{b\}$.
- $\delta: (Q \setminus F) \times \Gamma \to Q \times \Gamma \times \{L, R\}$: partial transition function.
- $b$: blank symbol (not in $\Sigma$).
- $q_0 \in Q$: initial state.
- $F \subseteq Q$: set of final (accepting) states.
Configuration: An element $w_1 q w_2 \in \Gamma^* \times Q \times \Gamma^*$, where the first letter of $w_1$ and the last of $w_2$ are not $b$.
Acceptance:
- $M$ halts on input $w$ if $q_0 w \vdash_M^* u q v$ for some end-configuration.
- $M$ accepts $w$ if $q_0 w \vdash_M^* u q v$ for some accepting configuration ($q \in F$).
- The language accepted by $M$ is: $$ L(M) := { w \in \Sigma^* \mid M \text{ accepts } w } $$

Recursively Enumerable (r.e.): $L \subseteq \Sigma^*$ is r.e. if $L = L(M)$ for some Turing machine $M$.
Recursive: $L$ is recursive if there exists a Turing machine $M$ such that $L = L(M)$ and $M$ halts on all inputs (total decider).

A total function $f: \mathbb{N}^k \to \mathbb{N}$ is Turing-computable if there exists a TM $M$ and a calculable coding function $\langle \cdot \rangle : \mathbb{N} \to \Sigma^*$ such that for all $n_1, \dots, n_k \in \mathbb{N}$, there exists $q \in F$ with: $$ q_0 \langle n_1 \rangle b \langle n_2 \rangle b \dots b \langle n_k \rangle \vdash_M^* q \langle f(n_1, \dots, n_k) \rangle $$

Definition (Radó, 1962): $BB(n)$ is the largest number of steps any $n$-state Turing machine (tape alphabet $\{0,1\}$, blank $0$) can run before halting, when started on an empty tape.
Known values:
- $BB(1) = 1$
- $BB(2) = 6$
- $BB(3) = 21$ (Lin & Radó, 1965)
- $BB(4) = 107$ (Brady, 1983)
- $BB(5) = 47,176,870$ (confirmed 2024)
- $BB(6) \ge 10^{10^{\dots 10}}$ (astronomically large)
Non-computability: The Busy Beaver function $BB: \mathbb{N} \to \mathbb{N}$ is not Turing-computable. Given oracle access to any $b(n) \ge BB(n)$, one could solve the Halting problem.
Growth: For every Turing-computable function $f$, there exists $n_f$ such that $BB(n) > f(n)$ for all $n \ge n_f$.

Define the diagonalisation language: $$ L_d := { w \mid w = \langle M \rangle, w \notin L(M) } = { \langle M \rangle \mid \langle M \rangle \notin L(M) } $$
Proposition: $L_d$ is not recursively enumerable. (Proof by diagonalisation).
Conclusion: There exist unsolvable decision problems.

Define the Halting problem: $$ H = { \langle \langle M \rangle, w \rangle \mid M \text{ halts on input } w } $$
Exercise (result):
- $H$ is not recursive.
- $H$ is recursively enumerable.

For $L \subseteq \Sigma^*$, let $\bar{L} = \Sigma^* \setminus L$.
Proposition: If $L$ is recursive, then $\bar{L}$ is recursive.
Proof idea: Swap accepting and non-accepting states, and add transitions to a new accepting state for all undefined transitions in the original machine.

Define the universal language: $$ L_u := { \langle \langle M \rangle, w \rangle \mid w \in L(M) } $$
Theorem: $L_u$ is recursively enumerable but not recursive.
Proof:
- $L_u$ is r.e. because there exists a universal Turing machine $M_u$ that simulates any $M$ on $w$.
- $L_u$ is not recursive: if it were, its complement would be recursive, and one could build a machine accepting $L_d$, contradicting the fact that $L_d$ is not r.e.

Formal proof ties to the Halting problem: if $BB$ were computable, one could decide whether an $n$-state machine halts by simulating it for $BB(n) + 1$ steps.

Turing machines correspond to Type 0 languages (recursively enumerable).
Other automata (finite automata, pushdown automata, linear-bounded automata) define subclasses (regular, context-free, context-sensitive) within the Chomsky hierarchy, highlighting the central role of TMs as the most general computational model.