Due: Wednesday, Feb. 6
Sipser, exercise 5.3.
Sipser, exercise 5.11. An easy solution comes from undecidable logics. You can assume the results that we discussed in class.
Sipser, exercise 5.18. Show how to reduce a PCP problem with an arbitrary alphabet to PCP with a binary alphabet. Hint: when you think you are using a large alphabet on a computer, the underlying alphabet is actually binary. But be careful not to gloss over important details. Check your ideas, and be critical.
Sipser, exercise 5.20(b). A 2DFA is a program with a finite amount of memory stored in the program itself. You can write a program with a fixed collection of variables, where each variable can only hold a single character, or a string of a fixed size. The program can move two heads back and forth over the input, and can tell when each head is at the left or right end of the input. It is not allowed to write anything on top of the input. The input is on a read-only tape. When the program wants to answer yes, it goes into a special yes state and stops. When it wants to answer no, it goes into a special no state and stops.
The problem is to show that the set of 2DFA programs that do not accept any strings is undecidable.
Hint. Reduce Post's correspondence problem to this problem. For any collection of dominoes you can write down a solution as a sequence of domino numbers. Show that, for any given collection of domino numbers, you can write a 2DFA program that recognizes correct solutions for the given PCP puzzle. Flesh this out into a proof that the set of 2DFA programs that accept no strings is not decidable.