CSE 431 Sample Midterm

1. (20 points) Give a brief, implementation-level description of a multi-tape Turing machine that shows that
   {x#y#z | x,y,z>= 0 are decimal integers and x=y+z} is in TIME(n).

2. (20 points) Show that the language BH={« M» | Turing Machine M halts when started at the left end of a blank tape} is undecidable.

   We prove that HALT_TM≤_m BH. Since HALT_TM is undecidable, this is enough.

   The reduction is as follows: Given a Turing machine M and input w to M, the function f will create a new TM (a familiar TM): M_w which ignores its input x and runs M on the hardcoded value w and does exactly what M does.

   f is certainly computable. It remains to show that f is a correct reduction.

   Now if (M,w) is in HALT_TM then M halts on input w and so M_w will halt on all inputs, including empty string input which corresponds to a blank tape. Therefore « M» is in BH.

   On the other hand if (M,w) is not in HALT_TM then M runs forever on input w and so M_w will run forever on all inputs, including empty string input which corresponds to a blank tape. Therefore « M» is not in BH.

   Therefore this is a correct reduction.

3. (20 points)

   1. Give the full formal definition of what it means for a set A to be mapping reducible to a set B.

   2. Prove that if a set C is co-Turing-recognizable but not decidable then it cannot satisfy C≤_m A_TM.

      If C≤_m A_TM then C must be Turing-recognizable. Therefore C is both Turing-recognizable and co-Turing-recognizable and hence decidable which is a contradiction.

4. (20 points)

   1. State the Church-Turing Thesis.

      "Turing machine algorithms capture our intuitive notion of algorithms" or "Any reasonable model that is strong enough to cover all of computation is equivalent in power to Turing machines.

   2. Why can't we ever prove the Church-Turing Thesis?

      It isn't a precise statement since it is about "intuitive" or "reasonable" notions of algorithm.

   3. What is the evidence for it?

      All the models that people have come up with like TMs, Lambda Calculus, Mu-recursive functions, standard programming languages, are equivalent.

   4. (This originally was about simulating a 2-dimensional TM by an ordinary one. Since you did that on homework, here is another one.) A queue automaton is a bit like a Turing machine except that it has a single queue of symbols instead of a tape. The input followed by a single blank symbol is initially in the queue with the first character at the head of the queue. In each step the queue automaton pops (reads and removes the symbol) at the head of the queue, and then, based on that symbol and the current state, changes state and pushes one or two symbols onto the tail of the queue. Explain why a queue automaton is equivalent to a TM. (The tricky part is seeing how you can simulate TM moves in each direction on the queue automaton.)

      The general idea is to use the queue together with the state of the queue automaton to keep track of the TM configuration. In general, configuration uqav will be represented as the queue string av#u where the head is on the a. The state will hold q.

      To do a right move delta(q,a)=(p,b,R) of the TM the queue machine will remove a from the head, change to state p, and add b to the tail, yielding queue contents v#ub.

      To do a left move delta(q,a)=(p,b,L) of the TM, suppose that the queue contents are av#uc. The queue machine will remove a from the head, add $b to the tail to reach v#uc$b and record that it will want to move to state p. Before that can happen it will move one character at a time from the head to the tail, provided that the following character is not $. (The putting on the tail will be one step after reading from the head.) At this point, it can end up with $bv#u and if we allow editing the head, we would replace the $ by the c it has remembered yielding cbv#u. (If editing of the head is not allowed, the $ can be read immediately and the remembered c can be used to trigger the next state change.)

5. (20 points) If language L is defined over alphabet Sigma then the set of prefixes of strings in L,
   Prefix(L)={x | there exists a y in Sigma^* such that xy is in L}.

   1. Show that if L is Turing-recognizable then Prefix(L) is Turing-recognizable.

      There are three different natural proofs of this:
      (1) Since L is Turing-recognizable there is an enumerator E for L. We create a recognizer M' for Prefix(L) as follows, M': "On input x run E but whenever E outputs a string w, check to see whether x is a prefix of w; if so, accept."
      (2) Since L is Turing-recognizable there is an enumerator E for L. We create an enumerator E' for Prefix(L) as follows. E': "Run enumerator E but whenever E prints a string w, E' also prints all prefixes of w."
      (3) Given a TM M that recognizes L, create a recognizer M' for Prefix(L) as follows: M' "On input x, for t=1 to infinity: for all y in Sigma^{sup* with length at most t, run M on input xy for at most t steps; if M accepts, then accept"

   2. Intuitively, why doesn't the method you used for part (a) also show that if L is decidable then Prefix(L) is decidable?

      This depends on the answer from part (a); If (1) then if there may be no such w, in which case the algorithm will run forever; if (2) then the list of strings is definitely not in lexicographic order even if the w are, because the prefixes are very short; if (3) then again, the algorithm will run forever if no y exists.

   3. (BONUS - Do not attempt unless you are finished early and have already checked over your paper) Actually come up with an example where you can prove that L is decidable but Prefix(L) is not decidable.