Turing machine to compare binary

Question

I am trying to write, using a Turing simulation, so in the form:
0 1 * r 0 0 0 * r 0 0 # * * 3 0 x * r 0 0 y * r 0

...a program that takes two binary values separated by a ">" e.g. 1010>111 which will halt-yes if left>right and halt-no is left>right.

I would like to compare solutions, if you're interested, leave your solution.

Answer 1

One way is to perform binary subtraction. So you would take the least significant digit from the right hand side and subtract it from the least significant bit of the left hand side. If a "1" is subtract from a "0", borrow from the digit at its left, ...etc. If there is no "1" to borrow from, then the left operand is less than the right operand.

If all digits of the right hand side have been processed for the subtraction, then check if at the left hand side there was a "1" as a result of a subtraction, or some unprocessed "1" remains. If so the left operand is greater than the right operand. If not, then both are equal.

To mark which digits at the left hand side have already been processed, write different characters, like O and I, instead of 0 and 1.

Here is a transition table for doing that:

state	read	write	move head	next state
start	0,1,O,I,>		right	start
start	_		left	take
take	0	_	left	takeZeroR
take	1	_	left	takeOneR
take	>		left	findOne
takeZeroR	0,1		left	takeZeroR
takeZeroR	>		left	takeZeroL
takeZeroL	O,I		left	takeZeroL
takeZeroL	_		right	lessIfOne
takeZeroL	0	O	right	start
takeZeroL	1	I	right	start
takeOneR	0,1		left	takeOneR
takeOneR	>		left	takeOneL
takeOneL	O,I		left	takeOneL
takeOneL	1	O	right	start
takeOneL	0	I	left	borrow
takeOneL	_		right	halt-less
findOne	1,I		left	halt-greater
findOne	0,O		left	findOne
findOne	_		right	halt-equal
borrow	1	0	right	start
borrow	0	1	left	borrow
borrow	_		right	halt-less
lessIfOne	1		right	halt-less
lessIfOne	O,I,>,0		right	lessIfOne
lessIfOne	_		left	moreIfI
moreIfI	>,0,O		left	moreIfI
moreIfI	I		left	halt-greater
moreIfI	_		left	halt-equal

And here is a snippet to see the Turing machine run with user input:

createTuring({
    transitions: [
        { state: "start",     read: "01OI>",         move: "R", nextState: "start"     },
        { state: "start",     read: "_",             move: "L", nextState: "take"      },
        { state: "take",      read: "0", write: "_", move: "L", nextState: "takeZeroR" },
        { state: "take",      read: "1", write: "_", move: "L", nextState: "takeOneR"  },
        { state: "take",      read: ">",             move: "L", nextState: "findOne"   },
        { state: "takeZeroR", read: "01",            move: "L", nextState: "takeZeroR" },
        { state: "takeZeroR", read: ">",             move: "L", nextState: "takeZeroL" },
        { state: "takeZeroL", read: "OI",            move: "L", nextState: "takeZeroL" },
        { state: "takeZeroL", read: "_",             move: "R", nextState: "lessIfOne" },        
        { state: "takeZeroL", read: "0", write: "O", move: "R", nextState: "start"     },        
        { state: "takeZeroL", read: "1", write: "I", move: "R", nextState: "start"     },        
        { state: "takeOneR",  read: "01",            move: "L", nextState: "takeOneR"  },
        { state: "takeOneR",  read: ">",             move: "L", nextState: "takeOneL"  },
        { state: "takeOneL",  read: "OI",            move: "L", nextState: "takeOneL"  },
        { state: "takeOneL",  read: "1", write: "O", move: "R", nextState: "start"     },        
        { state: "takeOneL",  read: "0", write: "I", move: "L", nextState: "borrow"    },        
        { state: "takeOneL",  read: "_",             move: "R", nextState: "halt-less" },
        { state: "findOne",   read: "1I",            move: "L", nextState: "halt-greater" },
        { state: "findOne",   read: "0O",            move: "L", nextState: "findOne"   },
        { state: "findOne",   read: "_",             move: "R", nextState: "halt-equal" },
        { state: "borrow",    read: "1", write: "0", move: "R", nextState: "start"     },
        { state: "borrow",    read: "0", write: "1", move: "L", nextState: "borrow"    },
        { state: "borrow",    read: "_",             move: "R", nextState: "halt-less" },
        { state: "lessIfOne", read: "1",             move: "R", nextState: "halt-less" },
        { state: "lessIfOne", read: "OI>0",          move: "R", nextState: "lessIfOne" },
        { state: "lessIfOne", read: "_",             move: "L", nextState: "moreIfI"   },
        { state: "moreIfI",   read: ">0O",           move: "L", nextState: "moreIfI"   },
        { state: "moreIfI",   read: "I",             move: "L", nextState: "halt-greater" },
        { state: "moreIfI",   read: "_",             move: "L", nextState: "halt-equal" },
    ],
    initState: "start",
    tape: "111>011",
});

<script src="https://trincot.github.io/turing.js"></script>