----------------------------------------------------------------
CSC 363H -- Fall 2004 -- Main solution elements for Assignment 1
----------------------------------------------------------------

 1. [15 marks]

    Show "recognizable by TM" iff "recognizable by 2-way infinite TM",
    by proving both directions of the "iff".

    (->)
    Given TM M, construct 2-way TM N as follows:
      - Place marker '#' to the left of input
        (where # is not in M's tape alphabet).
      - Run M: if # encountered,
        just move right and stay in same state.
    N behaves identically to M on all inputs, so
    every recognizable language is recognized by a 2-way TM.

    (<-)
    Given 2-way TM M, construct 2-tape TM N as follows:
      - N uses 2nd tape to keep track of portion of M's tape
        to the left of original input, in reverse.
    By Theorem 3.8, N can be simulated by a one-tape TM N', so
    every language recognized by a 2-way TM is recognizable.

 2. [20 marks]

    (->)
    f computable -> exists M that computes f(w) for every input w,
    following definition.
    Construct N as follows:
    N = "On input w#z:
      - Use M to compute f(w) on a blank portion of the tape.
      - Compare z with f(w): accept if they are the same, reject
        otherwise."
    Clearly, N decides L_f.

    (<-)
    L_f decidable -> exists M that accepts every string of the form w#f(w)
    and rejects every other string.
    Construct N as follows:
    N = "On input w:
      - Write w#u on unused portion of tape, where u = empty string, and
        use M to determine if w#u in L_f.
      - If M rejects, increment u to next string in lexicographic order
        and repeat with new w#u.
      - When M accepts, copy u = f(w) over to the start of the tape, erase
        the rest, and accept."
    Clearly, N computes f(w) given any string w, because there must be
    some value of u = f(w).
 3. [20 marks]

    A, B co-Turing-recognizable means A^C and B^C are Turing-recognizable
    (where A^C, B^C are the complements of A, B, respectively), i.e.,
    there are TM's M_A and M_B such that M_A accepts every string NOT in A
    and M_B accepts every string NOT in B.
    Consider the following TM:
    M = "On input x:
      - Simulate both M_A and M_B on x, in parallel.
      - If M_B accepts first, accept.
      - If M_A accepts first, reject."
    Because A, B are disjoint, one of M_A or M_B must accept (because every
    string is either not in A or not in B) so M is a decider.  Let C =
    L(M).  By definition, C is a decidable language.  Also, A subset of C
    because every string in A will be accepted by M_B but not by M_A (since
    A, B are disjoint).  Finally, B subset of C^C because every string in B
    will be accepted by M_A but not by M_B.

 4. [45 marks]

    (a) [25 marks]
        Very high-level idea: keep subtracting 1 (in binary) from x and y
        until one of them reaches 0; at that point, x has correct value.

        High-level description:
         1. Move the entire input one square to the right, to leave a
            blank square as a marker on the leftmost square.
            At the same time, scan the input for a single '-' character.
            If we find none or more than one, just move the head back to
            the start of the input and accept.
         2. (Now we know the string is in the form "x-y".)
            If x = 0 or y = 0, erase the "-y" part of the string, move back
            to the first character of x, and accept.
            Otherwise (x > 0 and y > 0), subtract 1 from y, subtract 1 from
            x, and repeat stage 2.

        High-level description of "subtract 1 in binary", when string is
        known to represent number greater than 0:
         1. Starting with rightmost character and moving left, repeatedly
            change 0's to 1's until a 1 is encountered and changed to 0,
            then move head back to leftmost character.

        Formal description: (to follow).

      (b) [10 marks]
        As in Theorem 4.9, we design a TM U' that simulates M on input w,
        with the addition that U' keeps track of the number of steps
        performed and rejects once t+1 steps have been simulated.  This can
        be done by using a separate part of the tape to count the number of
        steps of simulation performed and comparing it with 't' after every
        simulation step.

    (c) [10 marks]
        There are two possibilities to consider.
        Case 1:
            There is no limit to the length of possible runs of 3's in the
            decimal expansion of pi, in which case
                A_2 = {3}* = { e, 3, 33, 333, ..., 3^n, ... },
            which is easily decidable (use a TM that simply accepts
            everything).
        Case 2:
            There is a longest run of 3's in the decimal expansion of pi
            (say K 3's), in which case
                A_2 = { 3^i | 0 <= i <= K }
                    = { e, 3, 33, 333, ..., 3^K },
            which is also easily decidable (use a TM with K+3 states to
            accept if there are K or fewer 3's on the tape, reject
            otherwise).
        In either case, there is a TM that decides A_2.