CIT 596 Turing Machine assignment
Spring 2012, David Matuszek

Write the following three Turing machines.

  1. A TM that adds two binary numbers, separated by a +, and leaves the result as the only thing on the tape.

    For example: If the input is 10110+101, with the read head at the leftmost 1, then the result will be 11011, with the read head on the rightmost 1. You do not have to worry about the case where the read head starts in the wrong place.

    Suggested approach: Repeatedly subtract 1 from the number on the right and add it to the number on the left, until the number on the right consists of all zeros. Then erase the number on the right, along with the + symbol.

  2. A TM that compares two binary numbers, separated by =, and accepts the input if they are equal, or rejects the input if they are unequal.

    For example: If the input is 1011=1101, with the read head at the leftmost 1, then the machine will reject the input. You do not have to worry about the case where the read head starts in the wrong place.

    Suggested approach: X out the matching digits of the two numbers until either you find a pair of digits that don't match, or everything is X'd out.

  3. A TM that compares two binary numbers, separated by >, and accepts the input if the first number is larger than the second, and rejects the input otherwise.

    For example: If the input is 1011>1011, with the read head at the leftmost 1, then the TM will reject this input. You do not have to worry about the case where the read head starts in the wrong place.

    Suggested approach: Repeatedly subtract 1 from each of the numbers, until one or both of them consists of all zeros.

You can either:

Note 1: "Zip" means .zip; it doesn't mean Microsoft's proprietary .rar format or some other nonstandard format.

Note 2: Submit via Blackboard only before 6am Tuesday, March 27. Any other form of submission, such as email, will be ignored.