Example 9.11
Let x and y be two positive integers represented in unary notation. Construct a
Turing machine that will halt in a final state q y if x ≥ y, and that will halt in a
nonfinal state q n if x < y. More specifically, the machine is to perform the
computation
To solve this problem, we can use the idea in Example 9.7 with some minor
modifications. Instead of matching a's and b’s, we match each 1 on the left of the
dividing 0 with the 1 on the right. At the end of the matching, we will have on
Let x and y be two positive integers represented in unary notation. Construct a
Turing machine that will halt in a final state q y if x ≥ y, and that will halt in a
nonfinal state q n if x < y. More specifically, the machine is to perform the
computation
To solve this problem, we can use the idea in Example 9.7 with some minor
modifications. Instead of matching a's and b’s, we match each 1 on the left of the
dividing 0 with the 1 on the right. At the end of the matching, we will have on