Assignment V

Due date Nov.11.

1. A simple programming exercise: Write the quintuples for a Turing machine that transforms a unary string into its binary representation. Initially the input tape contains the number n in unary notation (alphabet: {1}). When the machine stops, the input has been erased, and the binary representation of n (alphabet {0,1}) is on the tape. To simplify matters, assume that the tape is unbounded in both directions, and that the final binary representation is written to the left of the original input. If the initial tape configuration contains the number 13:


then when the machine stops the tape looks as follows:


Use the standard algorithm: the remainder of successive divisions by 2 produces the digits from least significant to most significant. The tape alphabet includes a separator X, feel free to add more characters if it helps.
Try to minimize the number of states you use. It might be helpful to draw the machine as a graph, where each edge is labelled with the triple:
(input symbol, output symbol, direction)

2. From text: 3.17. Show as convincingly as you can that if a Turing machine cannot write on the portion of the tape that contains the input, if can only recognize regular languages.

3. From text: 4.15: show that the problem of determining whether a given DFA accepts a palindrome string is decidable. Hint: consider the DFA that recognizes the reverse language. Recall also that regular languages are closed under intersection. Your proof should be an informal description of an algorithm or Turing machine that starts from the encoding of the original DFA.

4. Explain why the language: { 1^n | n is a prime number} is decidable.