CSCI 6420
Spring 2009
Exercise Set 1

Write clearly readable and well thought out answers to all of the following questions. Turn in your work on Feb 16.

Some of these problems require reductions, which we have not covered yet. Work on problems as you become able to.

  1. What is the definition of a language?

  2. What is the definition of a computable language?

  3. Is every finite language computable? Explain.

  4. Is every infinite language uncomputable? Explain.

  5. What is the definition of the halting problem?

  6. We proved that the halting problem is not computable. What is the name of the proof method that we used?

  7. What is the definition of what it means for two programs to be equivalent?

  8. Let L1 be the language {(M, x, q) | M is (a description of) a finite state machine with alphabet {a,b}, x is a string in {a,b}*, and q is a state in M, where state number q is reached at some point while running M on input x. Show that L1 is a computable language.

  9. Let L2 be the language {M | M is (a description of) a finite state machine with alpabet {a,b}, and M accepts all strings in {a,b}*}. Is L2 a computable language? Prove your answer.

  10. Let L3 be the language {M | M is a Turing machine that accepts all prime numbers and rejects all nonprime numbers}. Is L3 computable? Prove your result.

  11. Let L4 be the language {(M, x, q) | M is (a description of) a Turing machine with input alphabet {a,b}, x is a string in {a,b}*, and q is a state in M, where state number q is reached at some point while running M on input x. Is L4 is a computable language? Prove your answer.

  12. What is the definition of an m-reduction between two languages?

  13. Define A = {(p,q) | p and q are programs, p(0) halts and q(0) loops forever}, and define B = {p | p(0) halts}. Give an m-reduction from B to A.

  14. Consider the following problem.

    Input: Two programs p and q (written in some agreed-on universal programming language)

    Question: Are programs p and q equivalent?

    Prove that this problem is not computable. Notice that you cannot use Rice's theorem directly for this, since Rice's theorem only talks about problems whose input is a single program, and here the input is a pair of programs. But you can reduce from a problem that you know is uncomputable by Rice's theorem.