A Case for Undecidability via Self-Reference

One of the major results that’s covered in most intro CS theory courses is that there are problem that are truly undecidable – there’s no general algorithm that can tell you the correct answer in all possible cases.

The typical way that undecidability is taught goes something like this:

• Students first see a concrete example of an undecidable language, like the halting problem. The proof that the halting problem is undecidable typically goes something like this:
• Assume that there’s a decider $D$ for the halting problem.
• Using $D$ as a subroutine, produce a machine $H$ that takes as input a TM $M$, then runs $D$ on $\langle M, \langle M \rangle \rangle$, then loops of $D$ says $M$ will halt on $\langle M \rangle$ and halts if $langle D$ says otherwise.
• Run $H$ on its own encoding $\langle H \rangle$. Contradiction!
• Students then use mapping reducibility as a mechanism for showing that other related languages are undecidable. Those proofs typically look like this:
• Given as input a TM $M$, construct a TM $D$ that runs $M$ on some input and has some complex behavior if $M$ halts on some input and has some other complex behavior if $M$ loops on that input.
• Use the fact that a TM that could decide whether $D$ has the property in question would decide the halting problem to show that the problem in question is undecidable.

When I first taught CS103, this is the approach I took to introducing undecidability, and I found it to be less than ideal for a number of reasons. First, the construction used to show that the halting problem (or, in my case, the language $A_{TM}$ of the universal TM) is undecidable is extremely tricky. It involves starting with a decider for the language and making a series of highly non-obvious transformations on it – converting it so that instead of taking two inputs, it takes a single input; building a new TM that listens for the result from the decider and then does the opposite; and finally running that TM on itself.

Second, once students had figured out how the construction worked, they had little intuition for what it was exactly about the halting problem that made it undecidable. “I can follow the proof,” they’d say, “but that still doesn’t give me a high-level intuition for how you’d eyeball this problem and have a hunch that it’s undecidable.” This is partly because the standard proof that the halting problem is undecidable is fairly technical and requires a number of non-obvious steps.

Third, students often had little intuition for how reducibility had anything to do with the intrinsic difficulty of problems. Part of this might have been specific to CS103: since the course doesn’t have algorithms as a prerequisite, for most students these sorts of impossibility reductions were the first exposure they’d had to reducibility. Many students thought that “reduction” mean “put a TM inside of a TM so that you can put that TM inside of another TM” and didn’t realize that there was a bigger-picture idea at play. Even after mastering the technique of proving undecidability via self-reference, many students expressed frustration that they understood how to execute a proof of undecidability, but had no idea why the reduction they’d done had proved anything.

In Fall 2014, I decided to abandon presenting undecidability using this above route and instead opted to use direct self-reference as a mechanism. After tuning and tweaking the presentation over the past three years, I’m very happy with how it’s worked.

This presentation of undecidability works in a number of stages. After first establishing the fundamentals (what decidability and recognizability mean, how languages connect back to the abstract notion of decision problems, how TMs work, etc.), I present a series of claims, in sequence, that build up to our first proof of undecidability:

• Universality is an emergent property of computation. It’s possible to build TMs that compute on other TMs and for TMs to run other TMs. (This introduces $A_{TM}$ and also is a great launching point for talking about why virtual machines, compilers, etc. are possible.)
• Self-reference is an emergent property of computation. I introduce an informal version of Kleene’s recursion theorem by showing how to write a Quine (with the strong caveat that what I’m doing is a proof of concept rather than something students are expected to know how to do!), then show how to write programs that do things like ask how many characters long they are or that print out whether they’re an even-length or odd-length program. I conclude by mentioning that, essentially, any program in any programming language can be modified to include a new function mySource() that returns the source code of the program.
• The combination of these two ideas leads directly to undecidability. Imagine you have a decider for $A_{TM}$, which we can model in software as a function willAccept(program, input) that takes as input the source code of a program and an input, then returns whether the program will accept the input. We then write this program, which asks whether it’s going to accept its input and then does the opposite:
• Generalize the above pattern. We can write all sorts of self-referential programs along the above lines to show that many different problems are undecidable without needing to appeal to reducibility.

From what I’ve seen, this approach offers several advantages over the version I outlined above. First, while there’s certainly some creativity involved in coming up with a self-referential program like the one above, the amount of effort required is lower than in the traditional proof that $A_{TM}$ is undecidable. There isn’t a complicated step of taking a two-input decider and turning it into a one-input decider, then flipping the accept and rejecting states, then running it on itself. This program is more of a “one-step” trick. The program asks what it’s going to do (is it going to accept its inputs?) and then proceeds to immediately do the opposite.

Second, this approach provides a powerful intuition for why many problems about TMs are undecidable. I often frame these sorts of self-referential constructions in terms of the classical trope of oracles and seers predicting the future. If you have a decider for a language about the observable behavior of TMs, you can think of it as an oracle (in the classical Greek sense rather than the complexity theory sense) that will predict the future by telling you what the program is or is not going to do. With self-reference, programs can then use such a decider to ask questions about what they themselves are going to do in the future, and therefore they can just decide to do the opposite of whatever is supposed to happen next. Students can point directly at the self-referential machine they construct as an explanation about why the problem they’re exploring is undecidable – they can say that this specific program will do the opposite of what it’s supposed to do if the underlying language is undecidable.

Finally, from a CS103 perspective, this approach is pedagogically useful for motivating reductions in a more practically-oriented setting. I touch on reducibility in the context of P and NP by showing it as a way of solving new problems using a solver for an original problem. For example, I show off how to solve the problem “given a box of connectors, can you find a way to plug your laptop’s VGA output into a projector’s HDMI input?” using a solver for the directed reachability problem, and the problem “given a crossword puzzle grid, how many dominoes can you place on it so that each domino covers two white squares and no dominoes overlap?” using a solver for maximum matching. As a first introduction to reducibility, I think these examples build a much better intuition for how reductions function than the computability “put a TM inside a TM inside another TM” reductions students would otherwise encounter first.

From experience, the sorts of questions I’ve gotten from students about this technique tend to be dramatically more focused and interesting than the questions I used to get about reducibility and the standard proof that the halting problem is undecidable. Students often ask about the limits of this technique – why can’t you use self-reference to prove that every language is undecidable, for example? – and about whether it generalizes to show that every language about TMs is undecidable. These are great questions and an excellent launching point for discussions of topics like Rice’s theorem.

There are still some bugs I need to work out of the presentation. I’ve been using C/C++-style pseudocode, which more students feel comfortable with than rather than high-level TM descriptions a la Sipser. This works well, but getting the right syntax down to make the learning as easy as possible is tricky and I think I still have some more work to do on that front.

There is also the shortcoming that this approach completely bypasses reducibility in the conventional sense. For the purposes of what I do in CS103 I think this is totally fine, though in other contexts this might not work out so well.

Going forward, I’m hoping to get this fully polished and to write a more in-depth explanation of the pedagogical decisions behind it and the supporting materials I’ve used to make everything click.