1
Universal TMs and the Halting Problem
Peter Dixon March 5, 2021
Admin stuff
HW6 is on nonregularity proofs with a bit of Turing machines HW7 is going to be all Turing machines
Then it’s exam time (no homework due exam week)
We’ll release a practice exam and solutions. I recommend trying to solve it without looking at the solutions, then get a small group together and grade each others’ solutions. THEN check the actual solutions. (Tbh I learned way more from grading classes than I ever did from taking them.)
There won’t be an additional exam review, but since no homework is due exam week, we’ll use office hours and recitations as essentially exam review.
Encoding Turing machines
2
• • • •
•
We can represent a Turing machine as a binary string. For example, we can encode the state and alphabet with 1a01b01c01s01t01r. We’re using 0 as a separator. 1a is the number of states, in unary. 1b is the size of the input alphabet, 1c is the size of the tape alphabet, 1s is the index of the start state (e.g. if the start state is state 2, this would be 11), and similarly for 1t and 1r.
For the transition function, we could do a series of terms 01w01v01x01y01z that say “If the wth state reads the vth character, then transition to the xth state, write the yth character, and move the tape head left if z = 1, right if z = 2.
This isn’t the most efficient encoding, but all we care about in this class is if it’s possible.
3 Universal Turing machines
We can make a Turing machine U that runs whatever Turing machine you give it. In other words, U(⟨M,x⟩) will accept if M(x) accepts, reject if M(x) rejects,
1
and loop if M(x) loops. We’re not gon get into exact details, cos it’s kind of hairy. We’ll use 3 tapes. Tape 1 will store the description of M. Tape 2 will store the current state. Tape 3 will simulate the tape of M. So the first thing wedoiswrite1s ontape2,writexontape3,anderasexfromtape1.
Then we have to repeatedly scroll through the description of M to look up which transition to take (based on the current state and tape contents), and update tapes 2 and 3 accordingly.
Again, it’s not too important for this class exactly how, we just want to know that it’s possible. If you want to know more about how, there are some fun examples of constructing UTMs in various contexts. In Magic: the Gathering, in esoteric programming languages, and in Conway’s Game of Life.
4 Languages of Turing machines
Since we have a way of getting a Turing machine as input, let’s look at what we
can do with Turing machines. First, we want to be able to check the syntax.
That is, we want to decide the language L = {x | x is a syntactically correct encoding of a TM}. Let’s list what we’d need to check:
• x is of the form 1a01b0….
• x has the correct number of 0s. (5, plus 5 per transition).
• There’s no missing or duplicate transitions.
• The tape alphabet is at least 2 bigger than the input alphabet. • The indices of s, t, r are all smaller than the number of states. • The move instruction is always 1 or 11.
• and so on.
We’re going to talk a lot about languages of Turing machines, and we’re going to kind of secretly include this in everything. So, we might want to decide
L = {⟨M⟩ | M (is a syntactically correct encoding of a TM that) has 20 states}. We’re going to drop that parenthetical and kind of assume that everything we get is a syntactically correct encoding of a Turing machine, because it’s possible to filter out syntactically invalid stuff.
L = {⟨M⟩ | M has 20 states} is decidable (pretty easily). But we’re going to talk about the big undecidable problem about Turing machines.
5 The Halting Problem
We can’t decide HALTTM = {⟨M,x⟩ | M(x) halts}. (M(x) halts if it eventually accepts or rejects.) The reason why is a similar proof to the diagonalization proof that the power set of an infinite set is even more infinite, or that the real numbers are uncountable.
2
Suppose there is a Turing machine H that can decide HALTTM. We’re going to build a machine G that H is wrong about.
We can encode TMs in binary, so we can list all valid encodings of Turing machines in order: Mλ, M0, M1, M00 . . . . Mλ is the shortest valid encoding of a Turing machine, M0 is the next shortest, and so on. (It doesn’t actually matter which Turing machine goes where – all we really need is a way to organize them.)
Since H can decide HALTTM for any TM/input pair, we’re going to make a big (infinite) table. On the top row is the list of Turing machines, while the side is a list of all binary strings. The table entry will be Y (meaning this TM/input pair halts) or N (meaning it don’t). The table could look something like this: (We don’t actually know what the table looks like because we can’t assume what H does. We don’t need to, though, because our argument doesn’t care if the table says Y or N in a particular place; it just says “do the opposite of what the table says”.)
Mλ M0 M1 M00 … λYNYN 0NNYN 1YYYY
00 N N Y Y
. …
Now we can define G. On input x, G will
1. compute Mx (by e.g. looping through all strings in order, and testing if
they’re TMs)
2. run H on ⟨Mx,x⟩
3. if H accepts, G immediately goes into an infinite loop
4. if H rejects, G immediately halts
Why does this prove that H doesn’t actually decide the halting problem?
Because G is somewhere in the list of Turing machines (we listed every Turing machine, after all). Maybe G is M0010, or maybe G is the something-billionth Turing machine. We’ll just say G is Mk. But G(k) does the opposite of what H thinks Mk(k) does.
In other words, we built G so that wherever G is in the enumeration, there is at least one string where G does the opposite of what H thinks.
Therefore, H doesn’t correctly decide HALTT M .
6 Another proof of the halting problem
This is a maybe slightly more intuitive proof, but it has a very tricky technical issue that we won’t get into how to solve.
Again, suppose H decides the halting problem. We’ll build M that 3
1. picks some string x
2. runs H(M(x))
3. if H accepts, M loops forever
4. if H rejects, M halts immediately
This is much simpler, except… how do you do step 2? How do you build a machine that can write down a description of itself? This is related to the idea of “quines” – programs that, when run, print their own source code. We won’t really get into this, so just take my word that it’s possible.
4