Turing Machines Basic Operations

Question

In this problem, you are expected to construct several Turing machines. For each Turing machine, provide a high-level description how it works and provide the graph representation. (You can leave out the formal definition if the graph is complete.)

a) Write a Turing machine T inc that can add 1 to a binary encoded number stored on the tape of the Turing machine. The binary number is enclosed by the symbol $ and you can assume that the binary number starts with a 0 (i.e., there is no overflow to consider). For example, the input $0100$ is transformed by T inc into $0101$ and the input $0111$ is transformed by T inc into $1000$ . The turing machine starts with the head located at the $ sign left of the number.

b) Write a Turing machine T dec that can subtract 1 from a binary encoded number stored on the tape of the Turing machine. The binary number is enclosed by the symbol $ . For example, the input $0100$ is transformed by T dec into $0011$ and the input $0111$ is transformed by T dec into $0110$ . The turing machine starts with the head located at the $ sign left of the number. Hint: You can invert all bits of the number, then add one to the number, then invert all bits of the number again.

c) Write a Turing machine T add that can add two binary encoded numbers on the tape of the Turing machine. The binary numbers are each enclosed by the symbol $ and you can assume that the binary numbers have a sufficient number of leading 0s to hold the sum (i.e., there is no overflow to consider). For example, the input $0100$0010$ is transformed by T add into $0000$0110$ , i.e., the first number was added to the second number.

Hint: You can construct T add out of T inc and T dec : While the first number is not zero, decrement the first number and increment the second number. Please name your states such that it is clear to which part of your textual description they belong. You may find it useful to write a Haskell program to simulate your Turing machines (i.e., following the example shown in class). This way you can run tests against your Turing machine to verify it is working correctly. Feel free to submit your Haskell code so that we can verify your design of the turing machines. Note that it is your responsibility to document things properly. If you hand in something we cannot understand, you will likely get zero points.

Answer 1

(a) To add 1 to a number in binary, you start with the least significant digit (looks like this is the last one on your tape), add 1 with carry, move left, and repeat with the carry from the previous step until the carry is 0. It is guaranteed the carry will be 0 at least once since the problem assumes you start with a 0 on the front of the tape. A TM might look like this:

Q    T    Q'    T'    D
-----------------------
// read the leading $
// reject if not there
q0   $    q1    $     right
q0   0    hR    0     same
q0   1    hR    1     same

// go to the last digit
q1   $    q2    $     left
q1   0    q1    0     right
q1   1    q1    1     right

// add 1 by swapping digit values
// reject if overflow
// accept if carry becomes 0
q2   $    hR    $     same
q2   0    hA    1     same
q2   1    q2    0     left

b) To subtract 1 from a number in binary, you start with the least significant digit, subtract 1 with borrow, move left, and repeat with the borrow from the previous step until the borrow is 0. This is either a trick question or it was ill-posed: given a number in this encoding, even with the assumption from part (a), it is not guaranteed that it is possible to subtract one: when presented with the encoding of zero, the required behavior of the TM is undefined. Assuming the number is greater than zero:

Q    T    Q'    T'    D
-----------------------
// read the leading $
// reject if not there
q0   $    q1    $     right
q0   0    hR    0     same
q0   1    hR    1     same

// go to the last digit
q1   $    q2    $     left
q1   0    q1    0     right
q1   1    q1    1     right

// subtract 1 by swapping digit values
// reject if underflow
// accept if borrow becomes 0
q2   $    hR    $     same
q2   0    q2    1     same
q2   1    hA    0     left

c) Forget the hint and just implement binary addition directly. It is not stated but heavily implied that the numbers have the same number of digits, or at least that the second number has more digits than the first. Add the least significant digits of both numbers, with carry, marking digits of the first and second numbers as you go, and finish when you run out of digits. Then, unmark the digits. Here's how your TM should process the example:

$0100$0010$
$0100C0010$
$010AC0010$
$010AC001A$
$01AAC001A$
$01AAC00BA$
$0BAAC00BA$
$0BAAC0BBA$
$ABAAC0BBA$
$ABAACABBA$
$0BAACABBA$
$00AACABBA$
$000ACABBA$
$0000CABBA$
$0000$ABBA$
$0000$0BBA$
$0000$01BA$
$0000$011A$
$0000$0110$