Turing Machine as Comparator
In this class, We discuss Turing Machine as Comparator
For Complete YouTube Video: Click Here
The reader should have prior knowledge of the Turing machine as a subtractor. Click Here.
We take an example and understand the Turing machine as a comparator.
a < b
a > b
a = b
The above comparisons were made using unary numbers.
The below diagram shows the example for a = b.
The two numbers, a and b, are differentiated using the symbol zero in the memory.
a = 3 and b = 3.
We convert the first one in the number a and the first one in number b.
We come back to convert the second number in a and move right to convert the second one in b.
On converting the first one in number a., we move right. If we see one, we move right.
The first number is over when we see zero, so move right to find one in the second number.
After converting the 1 in number b, move left till we find ‘x’ in number a.
We convert all ones in both numbers.
If a number a is over, we find zero. Then check for an extra one in number b.
If we find a blank, both numbers are equal, and
if we find an extra one, the number b is greater.
The below diagram shows the number b greater than a.
The below diagram shows condition a > b.
After finding one in number, a and blank is found on the number b. we say it a > b
The below diagram shows the compete Turing machine for the comparator.
On the state q0, if we see input symbol one, we convert to ‘x’ and move right.
The state q1 is used to move right till we find zero.
Once we find zero, the first number is over.
On the state q1, if we find input zero, we move right.
The state q2 is used to move right on the second number.
On the state q2, if we find the input symbol ‘x’, move right.
On the state q2, if we find the input symbol one, we convert to ‘x’ and move left.
Similarly, the state q3 is used to move back on the second number.
On state q3, if we find input symbol zero, we change to state q4.
The state q4 is used to move left on the first number.
On the state q4, if we see the input symbol ‘x’, we move right to find the next one in the first number.
On the state q2, if we find a blank symbol, we say a > b., so we move to halt state.
On the state q0, if we find input symbol zero, we move to state q5 to check for a > b or a = b.
On the state q5, if we find input one, we move to the halt state a < b.
On the state q5, if we find a blank symbol, we move to the halt state a = b.