Homework Exercise 2

Due: by 6pm on Wed 23 Jan
Worth: 1.5%

For each question, please write up your answers carefully: make sure that you use notation and terminology correctly, and that you explain and justify what you are doing. Marks will be deducted for incorrect or ambiguous use of notation and terminology, and for making incorrect, unjustified, ambiguous, or vague claims in your solutions.

  1. For any alphabet Σ, say that a function f : Σ* → Σ* is "computable" if there exists a TM M such that for all strings w ∈ Σ*, M accepts w with final configuration qA f(w), where qA is the accepting state of M. In other words, when M is started with w on its tape, it eventually enters its accepting state with only f(w) on the tape and its head on the leftmost symbol of f(w).

    Prove that a function f is computable (as defined above) iff the language Lf = {w#f(w) : w ∈ Σ*} is decidable (where # ∉ Σ).
    Give implementation-level descriptions in your proofs.

    Notes:

    • There is only one question for this exercise, because it is a little trickier than the typical level of difficulty for exercises.
    • This is an "if and only if": don't forget to prove both directions!
    • You are likely to find it helpful to write down a clear and precise definition of what it means for Lf to be decidable.
    • For one direction, note that the assumption that Lf is decidable (with decider ML) does not mean that M must somehow compute f. It is your responsibility to describe explicitly a TM that computes f (by making judicious use of ML).
      Hint: You may make use of the fact that it is possible for a TM to iterate on all of the strings over alphabet Σ.