Problem 1 (TM with Undo, 15 points). A TM with undo is the same as a basic single-tape TM, except in one computational step it is also allowed to perform the following “undo” action: Return the head to where it was before the most recent transition, and replace the symbol under the head with whatever was there previously. The state of the TM’s finite control should remain the same.
For example, suppose a TM with undo starts in configuration 8675p409. If its transition function specifies (p, 4) = (q, 3, R), then the next configuration will be 86753q09. If its transition function then specifies (q, 0) = U (where U stands for “undo”), then the next configuration will be 8675q409.
Things get more interesting when the TM with undo is asked to do multiple undos in succession, or interleave them with normal transitions. In these cases, the machine must be able to undo all of the normal transitions in the correct order – from most recent to least recent. If there is no instruction left to undo, the machine will stay in the same configuration.
For example, suppose the transition function of a TM with undo specifies (p,0) = (p,1,R), (p,1) = (q,0,R), (q,0) =U, (q,1) = (r,0,R), and (r,0) = (r,1) =U. Then if the TM’s starting configuration is p010, the next few configurations the TM with undo enters are
1. (read 0, write 1, move right)
2. (read 1, write 0, move right)
3. (undo instruction 2)
4. (read 1, write 0, move right)
5. (undo instruction 4)
6. (undo instruction 1)
7. (undo…but there is no instruction left to undo)
Give a simulation argument, using an implementation-level description, to show that every
language recognizable by a TM with undo is also Turing-recognizable.
Hint: It may be useful to maintain an explicit record of past actions in a stack. Every time the TM with undo performs a normal read/write/move transition, push a record of this action to the stack. And every time it performs an undo, pop the most recent action from the stack. How would you implement this behavior on, say, a multi-tape TM?
Problem 2 (Countability and Diagonalization, 18 points).
(a) An undirected graph is a finite set of vertices V ✓ N together with a finite set of edges
E = {{u, v} | u, v 2 V }. Show that the set G of all undirected graphs is countable. (8 points)
(b) Let M be the set of all encodings of Turing machines. A TM property is a function f : M ! {0, 1}. Use a diagonalization argument to show that the set of all TM properties, P = {f | f is a TM property}, is uncountable. (10 points)
Problem 3 (Loopy TM, 17 points). Consider the following computational problem. Given a TM M, does M loop forever on every input w?
(a) Formulate this problem as a language LTM. (3 points)
(b) Use a reduction to prove that LTM is undecidable. Make sure to explain (briefly) why the
TM computing your reduction is correct. (14 points)
Problem 4 (Bonus Problem). A function f : N ! N is non-increasing if f (i) f (i + 1) for every i 2 N. So f(1) = 8,f(2) = 3,f(3) = 2,f(4) = 2,… are the first few values of (what looks like) a non-increasing function f . But the function g where g(1) = 5, g(2) = 6, g(3) = 4, . . . is not non-increasing.
Is the set N I of non-increasing functions countable or uncountable? Prove your answer.