Computability and Complexity¶

From Computability, Complexity & Algorithms — Charles Brubaker and Lance Fortnow

This page is a comprehensive overview of the full course. Detailed notes for each topic are in their own files. The sections below give the full arc from formal languages through undecidability.

Part 1: Formal Languages and Countability¶

HSClassroom — The distinction between procedural (algorithmic) and mathematical (set-theoretic) definitions of functions — the starting point for computability theory.¶

Functions vs. Computability¶

Procedural function: a finite algorithm that computes output from input.
Mathematical function: any set of ordered pairs \((x, y)\) with unique \(y\) per \(x\).

Not every mathematical function is computable. Some functions require infinitely many steps on some inputs — they lie beyond any algorithm’s reach.

RulesofGame — A machine processing input to produce output — the basic computational model.¶

Strings and Languages¶

A string is a finite sequence of symbols from a finite alphabet \(\Sigma\). A language is any set of strings over \(\Sigma\).

SymbolStringLanguage — Hierarchy: symbols → strings → languages.¶

Language operations:

LanguageOpsQuiz — *Quiz:* Evaluate language operation expressions.¶

Countability¶

A set is countable if it is finite or in bijection with \(\mathbb{N}\).

OnetoOneCorrespondence — A bijection between integers and permutations demonstrates countability.¶

BinaryLanguageEnumeration — Enumerating all binary strings by length — strings over any finite alphabet are countable.¶

CountableUnionFinite — A countable union of finite sets is countable.¶

CountableUnionCountable — A countable union of countable sets is countable — proved by diagonal traversal.¶

AFalseProof — *Quiz:* Identify the flaw in this proof.¶

Diagonalization — languages are uncountable:

DiagTableIllustrated — Assume an enumeration of all languages. Construct a language \(L_D\) that differs from every enumerated language \(L_i\) on string \(s_i\) — \(L_D\) is not in the enumeration. Contradiction: the set of all languages is **uncountable**.¶

Key consequence: Programs are finite strings — countably many. But languages (equivalently, functions) are uncountable. Therefore uncountably many functions have no algorithmic solution.

Part 2: Turing Machines¶

TuringPortrait — Alan Turing (1912–1954), inventor of the Turing machine model.¶

PhysicalTM — A physical Turing machine — infinite tape, read/write head, finite control.¶

Arithbook — Motivating analogy: arithmetic done on paper with finite rules.¶

LongTheorem — Human computation is bounded by perception — machines extend this without limit.¶

Formal Definition¶

A Turing machine is a 7-tuple \((Q, \Sigma, \Gamma, \delta, q_0, q_\text{acc}, q_\text{rej})\):

\(Q\)	Finite set of states
\(\Sigma\)	Input alphabet (excludes blank \(\sqcup\))
\(\Gamma\)	Tape alphabet (\(\Sigma \cup \{\sqcup\} \subseteq \Gamma\))
\(\delta\)	\(Q \times \Gamma \to Q \times \Gamma \times \{L, R\}\) — transition function
\(q_0\)	Start state
\(q_\text{acc}\)	Accept state
\(q_\text{rej}\)	Reject state

TMDiagram — Turing machine components: tape, head, and finite control.¶

TMNotation — Mathematical notation for specifying a Turing machine.¶

Examples¶

TestOddnessExampleTM — TM testing whether a binary number is odd — check the last bit.¶

ConfigSequenceIllustration — A **configuration** is a snapshot: current state, tape contents, head position. Computation is a sequence of configurations.¶

TMEqualityTestExample — TM deciding \(\{w\#w \mid w \in \{0,1\}^*\}\) — match symbols across the \(\#\).¶

TMEqualityTestComputation — State-by-state trace of the equality-test computation.¶

TMConfigQuiz — *Quiz:* Determine the next configuration in a computation.¶

RightShiftQuiz — *Quiz:* Design a TM that right-shifts its tape contents by one cell.¶

BalancedStringQuiz — *Quiz:* Design a TM recognising balanced parentheses.¶

Deciding vs. Recognising¶

LanguageDeciders — A **decider** halts on every input — accepting members, rejecting non-members.¶

DecidesContainsOneQuiz — *Quiz:* Build a decider for strings containing at least one `1`.¶

DecideVsRecognize — A **recogniser** accepts members but may loop on non-members. Every decidable language is recognisable; the converse fails.¶

DefLanguageOfMachine — \(L(M)\) = the set of strings \(M\) accepts.¶

Part 3: Church-Turing Thesis¶

Thesis: Everything computable is computable by a Turing machine.

This is a thesis (not a theorem) — it cannot be formally proved, but is supported by the equivalence of all known reasonable computational models.

EquivalenceGraph — Computational models — multitape TMs, RAM machines, modern CPUs — are all equivalent in power to the standard single-tape TM.¶

Multitape Turing Machines¶

MultitapeDiagram — A multitape TM has several tapes with independent read/write heads.¶

DuplicateInputComputation — Example: duplicating input using two tapes.¶

SubstringSearchQuiz — *Quiz:* Design a multitape TM for substring search.¶

Simulation: A single-tape TM can simulate a \(k\)-tape TM by interleaving tape contents with markers for head positions.

MultiVsSingleTapeDiagram — Single-tape encoding of a multitape configuration.¶

MultiVsSingleTapeQuiz — *Quiz:* What is the overhead of the single-tape simulation?¶

StayputMachine — Simulating a “stay-put” head movement using left-then-right.¶

Random Access Machines (RAM)¶

RAMDiagram — A RAM machine: registers, indexed memory, and arithmetic operations — resembles a modern CPU.¶

RAMSimTuring — Pseudocode: RAM simulating a Turing machine (tape ↔ indexed memory).¶

TuringSimRAM — Multitape Turing machine simulating a RAM using tapes for registers and memory.¶

RAMVsMultiTapeQuiz — *Quiz:* What is the time overhead of TM-simulating-RAM?¶

Part 4: Universality¶

A Universal Turing Machine (UTM) accepts an encoded machine description \(\langle M \rangle\) and input \(w\), then simulates \(M\) on \(w\). This shows that programs are data.

Encoding¶

Simulation¶

TMInterpretation1 — Phase 1: the UTM reads the encoded description and sets up its tapes.¶

TMInterpretation2 — Phase 2: the UTM matches the current (state, symbol) pair against encoded transitions and executes the corresponding step.¶

Recognisability vs. Decidability¶

RecognizeVsDecide — Recognising: accept members, may loop on non-members. Deciding: accept members, *reject* non-members — always halts.¶

RecognizabilityVsDecidability — Relationship diagram: every decidable language is recognisable.¶

Theorem: A language is decidable \(\iff\) both it and its complement are recognisable.

Proof idea — alternating machines: Run two recognisers (one for \(L\), one for \(\overline{L}\)) in lock-step. Since every string belongs to exactly one, one recogniser must eventually accept.

AlternatingMachineCode — Pseudocode for the alternating-machines decider.¶

TwoRecognizersQuiz — *Quiz:* Which languages are recognisable / decidable given two recognisers?¶

Dovetailing¶

Recognisability Quizzes¶

CountingStatesQuiz — *Quiz:* Is \(\{\langle M \rangle \mid M \text{ has } \leq 10 \text{ states}\}\) decidable?¶

Halt34Quiz — *Quiz:* Is \(\{\langle M \rangle \mid M \text{ halts on } 34\}\) recognisable?¶

AcceptsNothingQuiz — *Quiz:* Is \(\{\langle M \rangle \mid L(M) = \emptyset\}\) recognisable?¶

AlwaysHaltingQuiz — *Quiz:* Is \(\{\langle M \rangle \mid M \text{ halts on every input}\}\) decidable?¶

Part 5: Undecidability¶

Diagonalization¶

AdjectiveTable — Diagonalization via English adjectives — the “heterological” paradox.¶

HeterologicalTable — The diagonal entry for “heterological” forces a contradiction.¶

TMTable — TM acceptance table — rows are machines \(M_i\), columns are encodings \(\langle M_j \rangle\).¶

TMDiagonalization — Flipping the diagonal shows that no machine \(M_L\) can recognise \(L = \{\langle M \rangle \mid \langle M \rangle \notin L(M)\}\).¶

DumaflacheQuiz — *Quiz:* Does diagonalisation apply to other computational models?¶

Mapping Reductions¶

\[A \leq_m B \;\iff\; \exists \text{ computable } f : w \in A \iff f(w) \in B\]

ReductionConsequences — If \(A \leq_m B\) then: \(B\) decidable \(\Rightarrow\) \(A\) decidable; \(A\) undecidable \(\Rightarrow\) \(B\) undecidable.¶

ConsequencesQuiz — *Quiz:* Apply reduction consequences.¶

SimpleReductionForm — Template: reduction from \(D_{TM}\) to show a new language \(B\) is undecidable.¶

WhichReductions — *Quiz:* Identify valid reduction directions.¶

The Halting Problem¶

\[H_{TM} = \{ \langle M \rangle \mid M \text{ halts on } \varepsilon \}\]

Filtering technique: reduction machines that conditionally simulate another machine.¶

Decidability Hierarchy Summary¶

Category	Example	Status
Decidable	String equality \(\{w\#w\}\)	TM always halts with correct answer
Recognisable (undecidable)	Halting problem \(H_{TM}\)	TM accepts “Yes” instances; may loop on “No”
Unrecognisable	Diagonal language \(L\)	No TM can even semi-decide it

Key Formulas and Definitions¶

Countability:

\[|\Sigma^*| = \aleph_0, \qquad |\mathcal{P}(\Sigma^*)| = 2^{\aleph_0} > \aleph_0\]

TM transition function:

\[\delta : Q \times \Gamma \to Q \times \Gamma \times \{L, R\}\]

Mapping reduction:

\[A \leq_m B \;\Longleftrightarrow\; \exists \text{ computable } f,\; w \in A \iff f(w) \in B\]

Decidability iff complement recognisable:

\[L \text{ decidable} \iff L \text{ recognisable} \land \overline{L} \text{ recognisable}\]

Diagonal language (unrecognisable):

\[L = \{ \langle M \rangle \mid \langle M \rangle \notin L(M) \}\]

Halting problem (undecidable, recognisable):

\[H_{TM} = \{ \langle M \rangle \mid M \text{ halts on } \varepsilon \}\]