CSE 431 Sample Midterm

The midterm will be Monday, Nov 4 in class. Here is a slightly modified version of one of my old 431 midterms. There will be a review session on Sunday, Nov 3 in ECE 037 starting at 4:15 pm.

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

  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.

  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 ATM.

  4. (20 points)

    1. State the Church-Turing Thesis.

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

    3. What is the evidence for it?

    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.)

  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.

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

    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.