Turing Machines and Computational Complexity

Turing Machines and Complexity Theory

Turing Machine

TM = (Q, Σ, Γ, δ, q₀, q_accept, q_reject): Q — states, Σ — input alphabet, Γ — tape alphabet (Σ ⊆ Γ), δ: Q×Γ → Q×Γ×{L,R} — transition function. Infinite tape, read/write head.

A TM is a theoretical model of a computer. The Church–Turing thesis: anything that can be computed intuitively can be computed by a Turing machine.

Complexity Classes

P: problems solvable by a DTM in polynomial time O(nᵏ).

NP: problems whose solutions can be verified in polynomial time. Equivalently: solvable by a nondeterministic TM in polynomial time.

NP-complete problems: every problem in NP is polynomial-time reducible to them. SAT (Cook, 1971), Clique, Coloring, TSP,...

P = NP? The key open problem of Computer Science. Most mathematicians believe P ≠ NP, but there is no proof.

Undecidable Problems

The Halting Problem: there is no algorithm which, given an arbitrary TM M and input w, determines whether M(w) halts.

Proof by diagonalization (Turing, 1936): assume there exists an algorithm H(M, w) → {halt, loop}. Construct M*: M*(M) = loop if H(M,M)=halt, and halt otherwise. Paradox when running M*(M*).

Rice's Theorem: Any nontrivial semantic property of Turing machine languages is undecidable.

The boundary between “decidable” and “undecidable” is a fundamental frontier of mathematics and Computer Science.

Turing Machine: Details and Variants

Multi-tape TMs: equivalent to single-tape but can be quadratically faster. Nonlinear TM: with an oracle; TM with probabilistic choices (PTM): probabilistic languages. Classes: P (deterministic polynomial time), NP (nondeterministic), PSPACE (polynomial space), EXPTIME. P ⊆ NP ⊆ PSPACE ⊆ EXPTIME — these containments are proven. P ⊊ EXPTIME strictly (time hierarchy theorem). P ≠ NP is a Millennium open problem; most containments inside this chain (P⊊NP, NP⊊PSPACE) have yet to be proven.

Undecidability of the Halting Problem (Turing, 1936): given a pair (M, w), will machine M halt on input w? The proof by diagonalization is one of the most elegant in mathematics. Suppose H(M, w) = 1 if M halts, 0 otherwise. Construct D(M) = if H(M, M) then loop else halt. Then D(D) — contradiction. This diagonalization technique is a direct analogue of Cantor's proof of the uncountability of ℝ.

Gödel’s Theorem and Incompleteness

Gödel’s incompleteness theorem (1931): Any consistent formal system containing arithmetic contains true but unprovable statements. Connection with computability theory: undecidability of the halting problem ↔ first incompleteness theorem (through encoding). The statement “program M does not halt” may be true but unprovable in PA (Peano Arithmetic). The Paris–Harrington theorem (1977) is an example of an arithmetic statement that is true but unprovable in PA.

Constructive Proofs: Some statements about algorithmic complexity cannot be proven in standard systems (PA, ZFC). Proofs of lower bounds on complexity often require new axioms or fundamentally new methods.

Descriptive Complexity and Algorithmic Information

Kolmogorov complexity K(x) — the length of the shortest program (in a fixed language) generating x. Random string: K(x) ≈ |x| (incompressible). Kolmogorov’s principle: almost every string of length n has K(x) ≥ n (random). Uncomputability theorem: K is undecidable — K(x) cannot be computed algorithmically for arbitrary x. Relation to Shannon entropy: E[K(X)] ≈ H(X) for a source X.

Undecidability: The Halting Problem and Its Consequences

The Halting Problem: Given TM M and input w, will M(w) halt? Undecidable — Turing’s diagonal argument. Consequences via reductions: emptiness problem for TM, equivalence problem for TM, language membership problem for TM. Rice’s Theorem: any nontrivial property of a TM’s language is undecidable. This is a powerful tool: proves undecidability without explicit reduction.

Complexity and Provability: Gödel’s Theorem

Gödel’s First Incompleteness Theorem: In a sufficiently strong formal system (containing arithmetic) there exist true statements that cannot be proven. Second theorem: The system cannot prove its own consistency. Connection with computability: Gödel’s theorem is proved via a construction analogous to the diagonal argument — self-reference and undecidability are tightly linked.

Quantum Computability and Complexity

BQP class: problems solvable by a quantum TM with error ≤ 1/3 in polynomial time. P ⊆ BQP ⊆ PSPACE. Whether inclusions are strict is unknown. Factoring (Shor): NP ∩ co-NP, in BQP. Search (Grover): O(√N) — quadratic speedup compared to classical O(N). Quantum supremacy: Google (2019) claims to have solved a sampling problem in 200 seconds, which would take a classical supercomputer 10,000 years—debatable, but a historic claim.

Oracle Models and the Hierarchy of Complexity Classes

Oracle A: The A-relative class P^A contains problems solvable by a TM with access to oracle A in polynomial time. The Baker–Gill–Solovay theorem: there exist oracles A and B such that P^A = NP^A and P^B ≠ NP^B. Consequence: diagonalization cannot resolve P vs NP. Toda’s Theorem (Toda, 1991): PH ⊆ P^{#P}. The entire polynomial hierarchy reduces to a single counting oracle — solving a #P-complete problem gives full power over PH.

Numerical Example: Diagonalization and the Halting Problem

Problem: Prove the undecidability of HALT by diagonalization (constructive illustration on 3 machines).

Step 1: Suppose there exists a deciding machine H(M, w): returns “yes” if M(w) halts, “no” otherwise.

Step 2: Build machine D(M): if H(M,M)=“yes”, then D loops; if H(M,M)=“no”, then D halts in 1 step.

Step 3: Run D(D). Case A: H(D,D)=“yes” (D halts on D) → by construction, D loops — contradiction. Case B: H(D,D)=“no” → D halts — contradiction.

Step 4: Both cases impossible → H does not exist → HALT is undecidable. Analogy to Cantor: D is a “diagonal” object that is in none of the listed rows. Toda’s theorem (1991): PH ⊆ P^{#P} — despite HALT being undecidable, a #P oracle solves all problems in the polynomial hierarchy, demonstrating the immense power of counting problems.