CSE 431 Sample Midterm

The midterm will be Friday, May 9 in class. Here is one of my old 431 midterms.

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

  2. (20 points) Show that the language BH={« M» | 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 (co-r.e.) 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. In Turing's original paper, he began his informal discussion of the Turing machine using, instead of a tape, a two-dimensional sheet of paper that was marked off in a rectangular grid of cells, was infinite in every direction, had only a finite number of non-blank cells at any time and on which one could move some constant number of cells in any direction after a step. Then, without proof, he said that one might as well assume that this had only a one-dimensional tape, infinite in only one direction. Describe a way that the one-way infinite tape in Turing's final version of the model can be used to store the information stored in the cells in his original two-dimensional sheet-of-paper model. (Hint: there are simpler ways of doing this but some form of dovetailing will work.)

  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.