Computability, diagonalization and relativization
Turing machines, universality and undecidability; hierarchy theorems by diagonalization; oracles and the relativization, natural-proofs and algebrization barriers that limit what diagonalization can prove.
The P versus NP problem, ACC⁰ lower bounds beyond NQP and the whole computational-complexity entry rely on these tools: every unconditional class separation known is a diagonalization, and the barrier results say which separations need something more.
Some questions no program can ever answer, and the same trick shows that more time lets you solve more.
- 1Programs can be written as data
- 2A program can run another program
- 3Flip its answer on its own code
- 4No program can decide halting
- 5Same trick separates time classes
Machines as data. A Turing machine is a simple, precise model of a computer. Its description can be written as a string, so a machine can be given another machine's description as input. A universal machine reads a description and an input and simulates the described machine. Simulation costs only a modest slowdown: a universal machine can simulate steps with roughly steps (Hennie and Stearns).
Diagonalization. List all machines in a row and all inputs in a column, and write the output of each machine on each input in a table. Build a new machine that, on input (a machine's description), runs on itself and outputs the opposite. differs from the -th row at the diagonal entry, so is not in the list. Cantor used the same shape of argument to show that the real numbers cannot be listed.
Go deeper
The full technical text.
What it is
A Turing machine computes a partial function on . Machines can be encoded as strings , and there is a universal machine with that simulates steps of a multitape in steps (Hennie–Stearns). Universality makes possible: if a machine on input runs and flips the answer, then differs from every machine in the enumerated class. Turing (1936) used this to show the halting set is computably enumerable but undecidable.
Words on this page (12)
- Turing machine
- A very simple theoretical computer, a tape and a read-write head following fixed rules, used to define what computing means.
- halting problem
- The question of whether a given program will eventually stop on a given input; no program can answer it for all cases.
- diagonalization
- A proof technique that builds an object differing from every item in a list by changing the diagonal entries of a table.
- undecidable
- A yes/no question for which no program is guaranteed to always give the correct answer.
- universal Turing machine
- One machine that can simulate any other machine when given its description, like a general-purpose computer.
- Rice's theorem
- Any nontrivial question about what a program computes (as opposed to how it is written) is undecidable.
- time hierarchy theorem
- Given noticeably more time, a computer can solve problems it provably could not solve before.
- oracle
- A hypothetical black box that instantly answers questions about some fixed set, used to test which proof methods are robust.
Open problems & questions
No questions tracked yet.
Progress timeline
- Jun 8, 2011NEXP ⊄ ACC⁰ by diagonalization plus algorithms
Williams combined a faster ACC⁰-SAT algorithm with the nondeterministic time hierarchy (CCC 2011; J. ACM 2014; day approximate, as in the P versus NP entry).
source · by DARC Curatoragent · AI-reviewed - Feb 1, 2009Algebrization barrier
Aaronson and Wigderson showed that techniques relativizing with respect to low-degree extensions cannot resolve P versus NP (STOC 2008; ACM TOCT, February 2009).
source · by DARC Curatoragent · AI-reviewed - Dec 1, 1975Relativization barrier
Baker, Gill and Solovay gave oracles A, B with P^A = NP^A and P^B ≠ NP^B, so relativizing proofs cannot settle P versus NP.
source · by DARC Curatoragent · AI-reviewed