===========================================================================
CSC 363H           Example of Turing machine description        Summer 2006
===========================================================================

Let f : {0,1,#}* -> {0,1,#}* be the partial function defined as follows:

 -  If w is a string of the form "x#y" with x,y in {0,1}*, then f(w) has
    length |x| and f(w) is a binary representation of the difference
    between the binary integer x and the binary integer y (if y is larger
    than x, then f(x#y) has value 0).

    For example, f(1001#010) = 0111, f(010#1001) = 000.

 -  If w does not have the form above, then f(w) is undefined.

    For example, f(01#11#00) and f(0100) are undefined.

Show that f is computable (see Assignment 1 for the definition of
"computable" for partial functions).

--------
Solution
--------

High-level description:  Keep subtracting 1 (in binary) from both x and y
until one of them reaches 0 (at which point x has the correct value), then
erase "#y" from the tape.

Implementation-level description:
 1. Move the entire input one square to the right, to leave a blank square
    as a marker on the leftmost square (this stage is unnecessary when
    using the alternate convention -- see below for details).
 2. Scan the input for a single '#' character and move the head back to the
    leftmost input symbol.  If we find no '#' or more than one, reject.
 3. (Now we know the string is in the form "x#y" and the head is on the
    leftmost symbol of x.)
    Scan to the right: if x = 0 or y = 0, erase the "#y" part of the
    string, move back to the leftmost character of x, and accept;
    otherwise, keep moving right to the rightmost non-blank square.
 4. (Now we know x > 0, y > 0 and head is on the rightmost symbol of y.)
    Scan to the left: subtract 1 from y, subtract 1 from x, move all the
    way back to the leftmost non-blank square, then go back to stage 3.

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

Formal description:
    Q = {q00, q01, q02, q03, q04, q05, q06, q07, q08, q09,
         q10, q11, q12, q13, q14, q15, q16, qA, qR}
    q00 is start state, qA is accept state, qR is reject state
    S = {0,1,#}
    T = {0,1,#,_}
    d is described by the following table, including comments to describe
    the purpose of groups of states -- transitions going to state " * "
    indicate a situation that can never happen, so the details of these
    transitions are meaningless:

                 0          1          #          _
            write _ on leftmost square (stage 1)
        q00  (q01,_,R)  (q02,_,R)  (q03,_,R)  (q16,_,L)
            move input one square right (stage 1)
        q01  (q01,0,R)  (q02,0,R)  (q03,0,R)  (q04,0,L)
        q02  (q01,1,R)  (q02,1,R)  (q03,1,R)  (q04,1,L)
        q03  (q01,#,R)  (q02,#,R)  (q03,#,R)  (q05,#,L)
            check that input contains exactly one # (stage 2)
        q04  (q04,0,L)  (q04,1,L)  (q05,#,L)  (qR ,_,L)
        q05  (q05,0,L)  (q05,1,L)  (qR ,#,L)  (q06,_,R)
            check that x > 0 (stage 3)
        q06  (q06,0,R)  (q07,1,R)  (q14,#,R)  ( * ,_,R)
        q07  (q07,0,R)  (q07,1,R)  (q08,#,R)  ( * ,_,R)
            check that y > 0 (stage 3)
        q08  (q08,0,R)  (q09,1,R)  ( * ,#,R)  (q15,_,L)
        q09  (q09,0,R)  (q09,1,R)  ( * ,#,R)  (q10,_,L)
            subtract 1 from y (stage 4)
        q10  (q10,1,L)  (q11,0,L)  ( * ,#,L)  ( * ,_,L)
        q11  (q11,0,L)  (q11,1,L)  (q12,#,L)  ( * ,_,L)
            subtract 1 from x (stage 4)
        q12  (q12,1,L)  (q13,0,L)  ( * ,#,L)  ( * ,_,L)
        q13  (q13,0,L)  (q13,1,L)  ( * ,#,L)  (q06,_,R)
            move head to right end of input (stage 3)
        q14  (q14,0,R)  (q14,1,R)  (q14,#,R)  (q15,_,L)
            erase "#y" part (stage 3)
        q15  (q15,_,L)  (q15,_,L)  (q16,_,L)  ( * ,_,L)
            move head to start of input and accept (stage 3)
        q16  (q16,0,L)  (q16,1,L)  (q16,#,L)  (qA ,_,R)

Q:  What changes would be necessary if we used the alternate convention
    (where the initial configuration has the leftmost square blank,
    followed by the input, with the head on the first input symbol)?
    Think about this for yourself before looking at the answer below!

A:  Eliminate states q00, q01, q02; the start state becomes q03; change
    the transition table as follows:

                 0          1          #          _
            check that input contains exactly one # (stage 2)
        q03  (q03,0,R)  (q03,1,R)  (q04,#,R)  (qR ,_,L)
        q04  (q04,0,R)  (q04,1,R)  (qR ,#,L)  (q05,_,L)
        q05  (q05,0,L)  (q05,1,L)  (q05,#,L)  (q06,_,R)
            ...everything else stays the same as before...