CS Theory: Homework

Q1. Show that a one-tape Turing machine that never moves its tape head left is equivalent to a deterministic finite automaton.

Q2. Formally define a Turing machine M that given a binary string on its input tape adds one to it and leaves the result on the input tape. Show the sequence of moves your Turing machine M makes on the input 1011 starting off from the configuration q₀1011 where q₀ is the initial state of M.

Q3. Show that there are potentially nine distinct ways of classifying a language L and its complement L^- as being (a) recursive, (b) recursively enumerable but not recursive, and (c) not recursively enumerable. Which of these ways are actually possible?

Q4. Are the recursive languages closed under the Kleene star operator? Briefly justify your answer.

Q5. Is the language L = {w_i|M_i does not halt on w_i} recursively enumerable? Here w_i is an encoding the i^th input string and M_i is an encoding of the i^th Turing machine. Use reductions and the diagonalization language L_d to prove your answer.

Q6. Is the language L = {M|M does not halt on ∈} recursively enumerable? Here M is an encoding of a Turing machine. Use reductions and the diagonalization language to prove your answer.