Undecidability

Hopcroft 2e §8.1 and §9.2. Everything else in this app runs something. This does not, and cannot: the results here are proofs that certain questions have no algorithm, and an animation of a machine deciding one would be a lie about the subject. What can be shown is the shape of the argument, and where each language ends up.

The two things you can work with are on their own pages: the diagonalization table, whose every cell is a real machine run under a step budget, and the reduction builder, which constructs A ≤ B and refuses when the direction is wrong.

Where the languages live — Fig. 9.2

A language is recursive when some Turing machine accepts it and always halts: on a string outside the language it stops and says so. A language is recursively enumerable when some Turing machine accepts it, with no promise about the strings outside — it may run for ever. §9.2.1 calls a problem decidable exactly when its language is recursive, and undecidable when it is not.

Fig. 9.2, with every language plotted in the innermost class that contains it. The full six-ring version, from the regular languages outwards, is on the hierarchy page.

See the whole hierarchy →

A language and its complement — §9.2.2

Complementation is the tool that pins a language to a ring. Theorem 9.3 says a recursive language has a recursive complement — swap the accepting and halting behaviour, which is safe precisely because the machine always halts. Theorem 9.4 says that if a language and its complement are both RE, then running the two machines in parallel decides the language, so it is recursive. Between them, five of the nine possible placements disappear.

Rows: where L sits. Columns: where its complement sits. Four of the nine are possible (§9.2.2, p. 377).
L \ complement of L	recursive	RE, not recursive	not RE
recursive	possible Both in the inner ring. Theorem 9.3 makes this the only option once either one is recursive.	impossible Ruled out by Theorem 9.3: if L is recursive then so is its complement.	impossible Ruled out by Theorem 9.3, for the same reason.
RE, not recursive	impossible Ruled out by Theorem 9.3 applied to the complement.	impossible Ruled out by Theorem 9.4: if both are RE, both are recursive.	possible One in the middle ring, the other outside — L_u and its complement.
not RE	impossible Ruled out by Theorem 9.3 applied to the complement.	possible The same, the other way round — L_d and its complement.	possible Both in the outer region. Neither has a Turing machine.

What the two classes are closed under

The pattern is worth naming before reading the table. The recursive languages are closed under the operations where a decision can be assembled from finitely many decisions, and complementation is the sharpest case. The RE languages give up complementation and gain homomorphism, because a machine that need never halt can search an unbounded space — and the recursive languages cannot afford to.

Choose a cell for the construction, or for the language that shows there is none.
Operation	Recursive	Recursively enumerable
Union · exercise
Intersection · exercise
Concatenation · exercise
Kleene closure · exercise
Complement
Homomorphism · exercise
Inverse homomorphism · exercise

Every row but complementation is Exercise 9.2.6, which the book sets and does not answer. Those answers are worked here and marked exercise; complementation is Theorems 9.3 and 9.4, printed.

What this page does not claim

Nothing here simulates an undecidable problem. The diagonalization table runs real machines under a stated move budget and reports a cell it could not fill as unanswered, which is the honest outcome and also the subject.
No page decides membership in L_u, the halting problem, or L_d. There is no algorithm to implement, and Theorem 9.6 and Theorem 9.2 are why.
The closure results other than complementation are the answers to Exercise 9.2.6, which the book sets without printing solutions. They are marked as exercise answers wherever they appear.