CS 301 Problem Set 10, Due Friday, April 6, 2012

  1. Consider a new version of the Turing machine that has one additional operation: “Bomb!” When it executes the Bomb operation, it self destructs and also usually injures or kills anybody within a 20 meter radius. It would certainly be nice to be able to determine whether such a Turing machine will Bomb on an particular input.
    Formalize this as a language, and prove that the language is undecidable. Hint: One very easy way to do the proof is with a pretty easy reduction.
  2. Prove that if A \leq_m B then also \overline{A} \leq_m \overline{B} where we are using \overline{A} to denote the complement of set A .
  3. If L mapping reduces to a finite, nonempty, language, does L have to be a finite language? If so, why; if not, give a simple counterexample.
  4. For each of the following languages, classify it as decidiable, undecidable but Turing-recognizable, or not Turing-recognizable. Justify the classification you use. In all the languages, anything of the form <M> is an encoding of a Turing machine. Our alphabet includes at least 0 and 1.
    1. \{0 \}
    2. \{ \langle M \rangle | 0 \in L(M) \}
    3. \{ \langle M \rangle | M \mbox{ is the only Turing Machine that accepts } L(M) \}
    4. \{ \langle M \rangle | \, |L(M)| \geq 2 \}
    5. \{ \langle M \rangle | M \mbox{ halts on all palindromes } \}
    6. \{ \langle D \rangle | D \mbox{ is the string encoding of a DFA } D \mbox{ and } L(D) = \emptyset \}
  5. For each of the following problems about software design or computer science, reformulate the problem as a formal language, and then give an argument that the corresponding language is undecidable. You are allowed to used reductions among different parts of this problem. At least for the first one, model it in terms of Turing machines.
    1. Dead code (dead state): Given a program and a particular input and a particular line number in the program (model this as a state of your Turing machine), does the program running on that input ever reach that line number?
    2. Given a program and a line number, can we determine whether that line number is reached on all inputs?
    3. Given a program and a file f, does the program always close f before exiting?
    4. Given a program and a variable x, is x always initialized before the first time x is used?
-- Main.sloan - 2012-03-31
Topic revision: r2 - 2012-04-02 - 23:49:02 - Main.ctanti2
 
Copyright 2016 The Board of Trustees
of the University of Illinois.webmaster@cs.uic.edu
WISEST
Helping Women Faculty Advance
Funded by NSF