Turing machine as Comparator

Approach for Comparator

1. Matching two numbers by comparing '1's
2. Example: 11101111 (3 and 4): compare '1's by marking them 'X' and 'Y' respectively
3. If '1's are remaining in left of '0' and in right of '0', '1' are finished, then formar is greater
4. If '1's are remaining in right of '0' and in left of '0', '1' are finished, then later is greater
5. If both '1' are finished then numbers are equal

---

TAPE movement for string "110111":

---

Explanation of TAPE movement

1. Input is given as "110111" (2 and 2)
2. Scan string from left to right
3. Mark '1' as 'X' and then move to right
4. Reach right of '0' and mark '1' as 'X' and move left
5. Reach 'X' in left of '0' and move one step right
6. Again mark '1' as 'X' and then move to right
7. Reach right of '0' and pass 'X', mark '1' as 'X' and move left
8. Reach 'X' in left of '0'(passing 'Y', '0' and '1')and move one step right
9. As '0' is there after 'X' that means all '1's are finished before '0'
10. Check for '1' in right of '0'
11. Pass '0', 'X' and there is '1' remaining that means second number is greater than first one
12. And final state for this will be "a<b"

---

State Transition Diagram
We have designed state transition diagram for adder as follows:

Comparator for a = b
1. This concept is similar to aⁿbⁿ

Comparator for a < b
2. When all '1's are finished in left of '0'

Comparator for a > b
3. When all '1's are finished in right of '0'


4. Final version of Comparator