Complexity theory asks how resources grow with input length, not how long a particular laptop takes on one input. Before measuring a computation, we must specify what counts as an input, an answer, and a step. A precise model also exposes a more basic limitation: some decision problems have no algorithm at all.
Why resources and models come first
A statement such as "this algorithm is fast" has no mathematical content until three things are fixed: the objects the algorithm receives, the operations it may perform, and the quantity being counted. Complexity theory fixes these choices once, so that statements about different problems become comparable and theorems about all algorithms become possible. A theorem of the form "no algorithm can do X" quantifies over every program anyone could write. Such a statement is meaningful only if "algorithm" has been given a definition that is precise enough to reason about.
This unit has two goals and a continuation. The first is to define decision problems, deterministic computation, and time bounds, and to see exactly why the encoding of the input belongs to the problem. The second is to prove, by two different arguments, that undecidable languages exist: a counting argument that shows they are abundant, and a diagonal construction that exhibits a specific one. The continuation applies the diagonal idea with a computable time cutoff and explains what further work is needed for hierarchy theorems.
A note on what is proved here. Everything marked as a theorem or proposition has a complete proof in this unit, except where a statement is explicitly labeled as an unproved dependency. The polynomial-overhead simulation between standard machine models and Bertrand’s postulate in the trial-division example are used without proof.
Models and decisions
Definition 4.1.1
(Languages and deterministic computation)
Fix a finite alphabet, such as . A language is a set of finite strings. A deterministic Turing machine decides if it halts on every input, accepting exactly the strings in . Its time on an input is the number of steps until it halts; its worst-case time at length is the maximum over all length- inputs. The class contains the languages decided by deterministic machines in time bounded by a polynomial in input length.
An encoding is part of a problem. For example, a binary integer has length about , so an algorithm taking steps need not run in polynomial time in the input length. Reasonable deterministic machine models simulate each other with polynomial overhead for time, so the class is robust under standard model changes; this simulation fact is used here without proof. The precise running-time exponent can nevertheless depend on the model.
A decision problem asks a yes-or-no question about an input, and a language packages the question as the set of inputs whose answer is yes. Nothing is lost by restricting to yes-or-no answers for the purposes of this unit. Computing a function can be recast as deciding a language of input-output pairs, and the hardness phenomena we study already appear in this simplest setting.
Two further notions are needed. A machine recognizes a language if it accepts every string of and accepts no string outside . On strings outside it may reject or run forever. Every decider is a recognizer, but the converse fails, as the halting problem will show. A language is decidable if some machine decides it, and recognizable if some machine recognizes it.
Time bounds and the class P
Definition 4.1.2
(Decision within a time bound)
Let be a function. A deterministic Turing machine decides within time if it decides and, for every and every input of length , it halts after at most steps. The class consists of languages decided by a machine that halts on every input and takes at most steps on all inputs of sufficiently large lengths, for some constant . Then , which agrees with the definition above, because a polynomial is bounded by for some and once .
The worst-case convention matters. A machine that is very fast on most inputs but needs steps on a single input of each length has worst-case time , and this is the quantity the definition records. Average-case behavior is a different subject and is not measured here.
Polynomial time earns its central role partly because it is closed under composition. If one polynomial-time procedure prepares the input for another, the combination is again polynomial time. The following proposition makes that precise, and its proof uses an observation that is easy to overlook: a machine cannot write more symbols than it has steps.
Proposition 4.1.3
(Polynomial preprocessing preserves P)
Let be a function from strings to strings computed by a deterministic Turing machine in time at most on inputs of length , and let be decided in time at most on inputs of length , where and are polynomials with nonnegative coefficients. Then is decided in polynomial time; hence .
Proof
(Proof of the composition bound)
On input of length , first run the machine for . It halts within steps. In each step it can visit at most one new tape cell, and the input already occupies cells, so at most cells are ever visited, and the output has length . Then run the decider for on . Its running time is at most . Since has nonnegative coefficients it is nondecreasing, so . The machine accepts exactly when . On a standard single-tape model, clean up and position the output using a polynomial number of steps, for example at most a constant multiple of . The two phases and this transfer cost have a polynomial bound.
Without the output-length observation the proposition would be false as stated for a careless reader. A first phase that is fast but produces a huge output would make the second phase expensive. The proof shows this cannot happen: the output length is controlled by the running time.
Encodings and input length
The central caution of this section is that the same procedure can be efficient or inefficient depending only on how the input is written. The following example, already used above, is the model case.
Worked example 4.1.4
(Input size changes the bound)
Repeatedly decrementing a positive integer takes iterations. If is written in binary using bits, then can be as large as ; thus this procedure has exponential worst-case iteration count in . With unary input , the same count is linear in the input length. These are different encodings and therefore different complexity statements.
The next example performs an exact count for a procedure that looks harmless, trial division.
Worked example 4.1.5
(Trial division is exponential in the bit length)
Consider the procedure that, given a binary integer , tests each with and declares composite if some divides . Take , which has bits. Since and , we get . So the procedure tests divisors whenever no divisor is found earlier. (This particular is a prime, so all tests are performed.)
For general , suppose the leading bit is , so that . Then , and a prime input forces at least divisions. For this lower bound is , consistent with the exact count above. For the bound is , over a billion divisions. By Bertrand's postulate, used here without proof, an -bit prime exists for every ; hence the worst-case number of divisions is . Now change the encoding to unary, so that the input length is . The number of divisions is at most , each costing a polynomial in , so the same procedure runs in polynomial time in . The algorithm did not change; the measure of input size did. (It is a known theorem that primality admits a polynomial-time algorithm in the binary encoding, but that is a different and much cleverer algorithm, and nothing in this unit depends on it.)
The lesson is that "polynomial in the number" and "polynomial in the length of the number" are different notions, and complexity theory means the second by default. Procedures whose cost is polynomial in the numerical value but exponential in the bit length are sometimes called pseudo-polynomial, and they will reappear whenever integers occur in an input.
Worked example 4.1.6
(The same numerical value in two encodings)
The integer is in binary, so its binary input length is four. A loop that decrements it to zero executes thirteen iterations; the bound gives . In unary the input is a string of thirteen ones, and the same thirteen iterations are linear in that input length. The arithmetic value is unchanged, but the size parameter in the complexity statement is different. One example cannot prove an asymptotic bound, yet it makes clear which quantity must be varied in the worst-case analysis.
Counting: most languages are undecidable
Before giving an explicit undecidable language, we show that undecidable languages must exist for a purely quantitative reason. There are too many languages and too few machines.
Proposition 4.1.7
(Undecidable languages exist)
There are only countably many Turing machines, hence only countably many decidable languages over . The set of all languages over is uncountable. Consequently some language over is not decidable.
Proof
(Proof by counting and Cantor diagonalization)
Every Turing machine has a finite description (its states, alphabet, and transition table) that can be written as a finite string over a fixed finite alphabet. The set of finite strings over a finite alphabet is countable: list them by increasing length, and within a length alphabetically. So the machines can be listed as , and each machine decides at most one language. The decidable languages are therefore contained in a list (for machines that do not decide a language, repeat a fixed decidable language such as the empty set).
Now list all binary strings as in the same length-then-alphabetical order and define
For each , the languages and disagree on the string , so . Hence appears nowhere in the list, and in particular is not decidable. The same argument applied to any proposed list of languages shows that no list contains all languages, so the set of languages is uncountable.
This argument is a pure existence proof. It says nothing about which languages are undecidable, and it suggests, correctly, that "typical" languages are undecidable and that the decidable ones are exceptional. It also foreshadows the mechanism of the next section: the string is used to query the th machine about itself, and the answer is then reversed.
An undecidable problem
Theorem 4.1.8
(The halting language is undecidable)
Let , using an effective encoding of machines and inputs. No deterministic Turing machine decides .
Proof
(Diagonal proof)
Suppose a decider exists. Construct a machine that, on input an encoding , runs on . If says that halts on its own encoding, loops forever; otherwise halts. Now run on . If it halts, the correct answer from forces it to loop; if it loops, the correct answer forces it to halt. Both cases contradict the assumed correctness of .
Proof X-ray
What the self-reference uses and what it forgets
Three things carry the argument. First, is assumed to be a decider, so it halts on every input and is a well-defined machine; this is where totality is spent. Second, the encoding is effective: can compute from mechanically. Third, the one non-obvious move is to feed its own description, so that the answer of about is exactly what is built to contradict: halts on if and only if reports that does not halt on . The contradiction closes because 's report is correct by assumption, and every other step is a mechanical construction, so the only thing that can fail is the existence of . If were merely a recognizer the argument would give nothing: when loops on , may itself loop, so loops as well and no contradiction arises, consistent with being recognizable.
The contradiction does not say that no particular machine-input pair can be analyzed. It says that one total algorithm cannot correctly resolve every encoded pair. A recognizer for does exist: simulate on and accept if it halts, but this recognizer runs forever on nonmembers. Deciding requires halting on both yes and no instances.
Counterexample mode
A simulator is not a decider
Claim: the machine that simulates on and accepts when the simulation halts decides , because it answers correctly whenever it answers. Counterexample: let be a machine with a single state whose only transition moves the head one cell to the right on every symbol, including the blank, and which has no halting state. On the input the simulation never finishes, so neither accepts nor rejects. This pair is not in , so a decider would have to halt and reject it. Hence recognizes without deciding it. The repair is not a cleverer simulator: the theorem above shows that no machine halts correctly on all pairs.
Common mistake
(Undecidable versus expensive)
An exponential-time algorithm is still an algorithm that halts on every input. Undecidability rules out every decider, regardless of time bound; it is not merely a claim that the best algorithm is slow.
Concept lensStructural
Decidable means both sides are recognizable
A language is decidable exactly when both it and its complement are recognizable: run the two recognizers in alternation, one step each, and exactly one of them eventually accepts. Hence the complement of , which is undecidable although is recognizable, is not recognizable.
Practice and solutions
Quick check
(A procedure runs for iterations on a binary encoding of . Give a worst-case bound as a function of the bit length .)
Solution · Answer
Since , the number of iterations is less than ; inputs near show an exponential worst case.
Quick check
(Explain why simulation of on recognizes but does not decide .)
Solution · Answer
If halts, simulation eventually observes this and accepts. If never halts, simulation never finishes, so it fails the requirement that a decider halt on every input.
Quick check
(A trial division procedure tests all with on a binary integer with bits and leading bit . Show that at least divisions are performed whenever has no divisor in that range.)
Solution · Answer
A leading bit gives , so and . The tested divisors are , which number . If no divisor exists, every one of these tests is carried out.
Quick check
(A function is computed in time , and a language is decided in time on inputs of length . Give a polynomial bound for deciding and state its degree and leading coefficient.)
Solution · Answer
The output length is at most , so the second phase takes at most steps and adding a polynomial transfer cost gives a polynomial bound. The bound has degree and leading coefficient , because the transfer term has lower degree.
Quick check
(How many distinct languages are contained in the set of binary strings of length at most ? In general, how many are contained in the set of binary strings of length at most ?)
Solution · Answer
There are binary strings of length at most (the empty string, two of length one, four of length two), and each language is a subset of these strings, so there are languages. In general there are strings of length at most and therefore languages.
The continuation “Reductions, recognizers and time-bounded diagonalization” develops reductions and the later diagonal construction.