CSC 363 Winter 2007 — Assignment 1

Due: 2pm on January 26th. See course webpage for up-to-date information on due date.
Worth: 10% of your course grade.


  1. [20 marks]

    Given a string a, we denote by int(a) the non-negative integer obtained by interpreting a as a binary number. For example, int(00010) = int(10) = 2 and int(1011) = 11. For the empty string ε, define int(ε) = 0.

    Write a high-level description, an implementation description, and a formal description (as defined near the top of page 157 of the textbook — p.145 in the first edition) for a Turing machine that decides the following language L1 over the alphabet {0,1,#}*.

    L1 = { a#b : a, b ∈ {0,1}* and int(a) = int(b) + 3 }

    For example, 0011# and 100#1 ∈ L1, but 1101#10 ∉ L1.

    Justify briefly that your machine is correct.

  2. [20 marks]

    So far, we have studied the notion of computability from the point of view of recognizing languages. For this problem, you will consider the notion of computability as it applies to functions.

    For some alphabet Σ, we say that a function f : Σ* → Σ* is computable if there exists a Turing machine M such that for all strings w ∈ Σ*, M accepts input w with final configuration qaccept f(w). In other words, when M is started with input w on its tape, it eventually enters its accepting state with only f(w) on its tape and its head on the first symbol of f(w).

    Show that a function f is computable iff the language Lf = { w#f(w) | w ∈ Σ* } is decidable (where # is a symbol not in Σ).

  3. [20 marks]

    A 2-head Turing Machine has a regular one-way infinite tape and 2 heads that can operate independently of one another. The transition function of a 2-head TM is of the form

    δ(q, a, b) = (q′, a′, b′, D1, D2)

    where q, q′ are states, a, b, a′, b′ are tape characters, and D1, D2 are directions Left or Right. This transition says that, if the TM is in state q, head 1 reads a and head 2 reads b, the next state is q′, head 1 replaces a by a′ and moves in the direction D1, and head 2 replaces b by b′ and moves in the direction D2. We adopt the convention that if the two heads try to simultaneously write something on a tape cell, the character written by head 1 ends up on the tape. As usual, neither head can move off the left end of the tape.

    Show that 2-head TMs are equivalent in power to regular TMs. In your proof, give implementation-level descriptions of TMs.

  4. [20 marks]

    Given a language L, define another language L′, over the same alphabet, as follows.

    L′ = { w : all prefixes of w are in L }

    Note that we consider the empty string ε and w itself as prefixes of w.

    1. [10 marks] Show that if L is decidable, then L′ is decidable.
    2. [10 marks] Assume that L is recognizable but not necessarily decidable. What can you conclude about L′? Prove your claim.