Overview / Logistics

The purpose of this problem set is to get you practice designing and reasoning about Turing machines. As we've seen, they are very similar to DFAs, but they have two seemingly innocuous twists: they can write to the tape (which has an infinite capacity in both directions), and they can move the tape both to the left and to the right. Amazingly, these are the only changes we need to make to a DFA to create a mathematical model of a machine powerful enough to compute everything that we can compute with ordinary programming languages like Java.

Problem 1 (3 Points)

Click here to read a brief biography of Alan Turing, the inventor of the Turing machine. His story is as tragic as it is fascinating. Reflect on the following in a brief writeup:

• What were Turing's major technical accomplishments/contributions?
• What was Turing's "crime" for which he was convicted? What was his sentence? How long did it take for him to get pardoned for this "crime"? Does this surprise you?
• What do you think would have happened if Turing had been allowed to be who he was and he had continued to make contributions into the internet age? What kinds of problems would he have worked on in the '90s given his thought style?

Problem 2 (3 Points)

Create a Turing machine that recognizes the language with twice as many zeros as ones. (Note that this language is also context free, but sometimes it's interesting to see how to change it up with a different computational model).

Below are some tests you can try (Click here to download them for loading into multiple run)

Input	Result
101001010001001000	Accept
110000001001000111000010	Accept
001001	Accept
100011001001001000	Accept
0010100010101001	Reject
0100000010	Reject
100111000111000010010100	Reject
110010000001010	Accept
0001000100001011111101001001	Reject
0001000101	Reject

Problem 3 (3 Points)

We saw in class that it is possible to design a Turing machine that recognizes the language

\[ L = \{ 0^{2^N}, N \geq 0 \} \]

Or, in other words, the language of strings of 0s in which the number of 0s is a power of 2. As it turns out, the Turing machine is the only model we've seen so far powerful enough to recognize this language. Prove that this language is not context free.

Problem 4 (4 Points)

Given the input alphabet Σ = {0, 1, +, =}, create a multi-tape Turing machine in JFLAP to recognize the language ADD = {a=b+c| a, b, c are binary strings and a is the sum of b and c}. It's neat that we can finally do this, because we showed that this language is nonregular in homework 4, and you can use the CFG pumping lemma to show that it's also not context free.

Below are some random tests you can apply to your machine. Your machine should handle a's, b's, and c's of different lengths.

NOTE: I was seeing some strange nondeterministic behavior when trying to do "Fast Run" or "Multiple Run," but these should all give correct answers if you "step"

Input	Result
1011010=11+0	Reject
10000=100+1100	Accept
11110000=1101110+10000010	Accept
100101=11011+1010	Accept
100000110=110101+1111110	Reject
1101000=1+1	Reject
10010=1001+1001	Accept
110011=10111+11100	Accept
101100=1101+11111	Accept
10100=111+101	Reject

Problem 5 (3 Points)

Turing's ghost visited Dr. Tralie in his sleep and left him with a very special gift of a Turing machine that can actually stay put in addition to moving left and right, so the transitions were of the form

\[ \delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{ L, S, R \} \]

(where you recall that Q are the states and Γ is the tape alphabet). Dr. Tralie brought this machine in to show the class, but unfortunately, while he left the class unattended for a moment, someone jammed the "move left" mechanism and it that doesn't work anymore, so it can only stay in place or move to the right, with transitions of the form

\[ \delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{ S, R \} \]

This is a real pity, because this really weakens the machine. In particular, it's no more powerful than a DFA now. Prove this. You will have to show both directions; i.e. any DFA can be converted into a machine of this form, and that any machine of this form can be converted to a DFA. This will establish that the recognize the same class of languages.

Problem 6 (3 Points)

Someone asked in class what would happen if we replaced the stack in a PDA with a queue; that is, a data structure that only removes/reads things from the left and adds things to the right (like a line). Prove that with this change, such a "queue automaton" is as powerful as a Turing machine. As in the above problem, you will have to prove two directions to establish that they recognize the same classes of languages

1. Any queue automaton can be converted into an equivalent Turing Machine
2. Any Turing machine can be converted into an equivalent queue automaton. By a queue automaton, I mean a pushdown automaton where we replace the stack by a queue ADT with the following operations:
   • push(x): Add x to the right
   • pop(): Remove and return the element from the left
   • peek(): Return the element at the left, but do not remove it

As a hint, the first direction is more straightforward if you use a multi-tape Turing machine, which we know has the same power as a regular Turing machine. For the other direction, you will need to use what seems like a pretty limited data structure (the queue) to simulate moving left/right on a tape. To this end, consider how you might use a queue in a "circular fashion" by removing things from the left and adding them back to the right, while also keeping track of where the end of the tape is. Then, explain how to use this technique to move either left or right on the tape. Do not worry about efficiency.

As a final hint, the most difficult direction in the reduction from a turing machine to a queue automaton is moving the head to the left. Consider how you might use the states in the queue automaton to "remember" something that helps you here, and give a high level description of how that might work.