CS385, Fall 2008
Theory of Computation
Problem Set 10 (due Nov. 25)

This page is located at http://www.cs.bc.edu/~alvarez/Theory/PS10/

  1. Suppose that L is a Turing-enumerable language and that its complement L' is also Turing-enumerable.

    a) Give a high-level description of a decider Turing machine D that recognizes L. Your description should state what steps D goes through in order to carry out its computation on a generic input string w. The operation of your machine should be based directly on the use of enumerator machines for L and L', without relying on the fact (proven in class) that a language is Turing-recognizable if and only if it is Turing-enumerable.

    b) Provide explanations for each of the following based on your design from part a):

    1. Why the machine you described is a decider

      and

    2. Why your machine recognizes L.

  2. For each of the following languages L, determine whether L is decidable or not. If you state that L is decidable, give a high-level description of a Turing machine that decides L. If you state that L is not decidable, give a general argument that shows that no Turing machine can decide L. Explain carefully in any case.

    a) L = { <M, w> | M is a Turing machine, w is a string over the input alphabet of M, and the computation of M on input w involves at least 2000 computation steps (state transitions)

    b) L = { <M, w> | M is a TM that either rejects string w or loops forever on input w }

    c) L = { <M, w> | M is a TM that rejects string w }