===========================================================================
CSC 363                    Homework Assignment 1                  Fall 2008
===========================================================================

Due: by 2pm on Wed 1 Oct
Worth: 8%

For each question, please write up detailed 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.  In dyadic notation, integers are represented in base 2 using the digits
    1 and 2 (instead of 0 and 1).  For example, the integer 13 is
    represented by the dyadic string "221" because 13 = 2 * 4 + 2 * 2 + 1.
    Dyadic notation has one interesting property: each integer has a
    /unique/ representation, because there cannot be any leading digits.
    This is unlike binary notation, where each integer has infinitely many
    representations (for example, each of the infinitely many binary
    strings "1101", "01101", "001101", "0001101", ... represents the same
    integer 13).  In particular, note that the integer 0 is represented by
    the empty string (\epsilon) in dyadic notation.

    Give a decider for language

    SORTED = { [a_1, a_2, ..., a_n] : n (- N, a_i (- {1,2}* for 1 <= i <= n
               and a_1 <= a_2 <= ...  <= a_n using dyadic notation }.

    To be clear, the input alphabet for your TM will consist of the symbols
    '[', ']', ',', '1', '2', and your TM should accept all strings that
    represent a non-decreasing list of integers, rejecting all other
    strings (those that represent lists not sorted in non-decreasing order,
    and those that do not represent lists).

    For example, "[]" (- SORTED (it represents the empty list, which is
    vacuously sorted) and "[,]" (- SORTED (it represents the sorted list
    [0,0]), but "[1,]" !(- SORTED (it represents the unsorted list [1,0])
    and ",,][" !(- SORTED (it doesn't even represent a list).

    Give a high-level description (the main idea in one paragraph), an
    implementation-level description (a numbered list that describes
    details of head movements and tape contents, but does not mention
    states), and a formal-level description (full transition table or
    transition diagram, as well as an explicit list of the tape alphabet)
    of your TM.  Make sure to relate your formal-level description to the
    equivalent stages in the implementation-level description.


2.  A partial function is one that *may* be undefined for certain values in
    its domain.  For example, over the real numbers, 1/(x-2) is undefined
    at x = 2 and x^{1/2} is undefined for all x < 0, but x^2 is defined
    everywhere.

    "Partial Function Computers" (PFCs) are similar to TMs except that they
    are used to compute partial functions rather than to recognize
    languages.  More precisely, PFCs have only one halting state q_H
    (instead of the two halting states q_A, q_R), and we say that a PFC C
    computes the partial function f : \Sigma* -> \Sigma* if C has the
    following behaviour, when started in initial configuration "_ q_0 w"
    (for any string w (- \Sigma*): if f(w) is defined, then C's computation
    eventually terminates (in state q_H) with f(w) writen on its tape; if
    f(w) is undefined, then C's computation never terminates.
    A partial function is "computable" if there is some PFC that computes
    it.

    Prove that for all partial functions f : \Sigma* -> \Sigma*, f is
    computable (according to the definition above) if and only if the
    language
        L_f = { w#f(w) : w (- \Sigma* and f(w) is defined }
    is recognizable (where # !(- \Sigma).


3.  A "double-scan" Turing machine (DSTM) is similar to a regular TM,
    except that the head always reads and writes two squares at a time, and
    always moves two squares at a time.  Formally, the transition function
    of a DSTM takes input in Q-{q_A,q_R} x \Gamma^2 and produces output in
    Q x \Gamma^2 x {L,R}, where 'L' means "move two squares to the left"
    and 'R' means "move two squares to the right" -- as for a regular TM,
    the head does not move if the TM attemps to move left while scanning
    the two leftmost squares.

    Prove or disprove that DSTMs are equivalent to TMs.  Give *detailed*
    implementation-level descriptions in your answer.


4.  Consider the function f : {1}* -> {1}* defined as follows.

        f(x) = \epsilon  if x occurs as a string of consecutive digits
                somewhere in the decimal expansion of \pi;

        f(x) = 1^k  if x does /not/ occur anywhere in the decimal expansion
                of \pi, where 1^k is the longest string of consecutive 1's
                that occurs anywhere in the decimal expansion of \pi.

    For example, suppose 1111 = 1^4 is the longest string of consecutive
    1's that occurs anywhere in the decimal expansion of \pi (i.e., the
    decimal expansion of \pi does not contain five 1's in a row anywhere).
    Then, f(\epsilon) = f(1) = f(11) = f(111) = f(1111) = \epsilon and
    f(1^5) = f(1^6) = ... = 1111.

    Show that f is computable (using the definition of "computable" given
    in class for total functions).  Give both implementation-level and
    formal-level descriptions in your answer.

    /Hints/:  You *cannot* assume that \pi contains every possible finite
    sequence of digits (this is a conjecture, not a known fact).  And
    although an argument can be made that there exists a TM that computes
    successive digits in the decimal expansion of \pi, you do not need this
    fact in order to answer the question.  Instead, think of the possible
    values that the function can have, and reduce the question to the
    computation of a different function with the same values -- consider
    breaking down your answer into various cases.