# Turing machine for $u<v$ with $u$ and $v$ positive binary numbers

I was wondering how would I go about constructing a Turing machine that accepts $u < v$ with $u$ and $v$ positive binary numbers: for example $10<100$ is accepted but $11<10$ would not be. (We can assume that the leftmost digit is always a $1$). I was thinking that I should start by changing the $1$s to $X$s but that doesn't seem to work out.

• Damnit, Alan Turing deserves a capital letter. – David Richerby Oct 28 '16 at 15:30
• Forget about Turing machines for a minute and think about how you would determine whether one binary number is bigger or smaller than another one by looking at the bits. Then try to figure out how to implement that with a Turing machine. (Don't convert to decimal because then you have to solve essentially the same problem again because then you need to determine whether one decimal number is bigger than another by looking at the digits.) – David Richerby Oct 28 '16 at 15:33
• If I understood correctly you have two numbers given in binary and have to compare, so maybe you could write binary subtraction? If you dislike the idea, then start from checking lengths of both numbers, if they match compare the most significant bit, erase if equal or stop with the result if not, otherwise since the numbers are positive integers the length mismatch also gives you result. Now after implementing this in your own favourite language translate it to Turing's machine code. – Evil Oct 28 '16 at 17:19

So, firstly let's define the input tape. Let's say it looks like "10101<00101" i.e. "number1< number2" and accepts only if the expression is true. Also, let the head in the start be on the most left meaningful character. The idea of the algorithm is just to scan two numbers from the left (assuming big-endian encoding for the numbers), if noticed that there is 0<1 accept immediately, if 0<0 or 1<1 then continue working, if 1<0 then reject.

So, TM sketch:

alphabet is $\{0,1,*,<\}$ with empty symbol $\epsilon$.

Record the most left bit of the first number If it is 0 you change you state to something like num1_0 which means number 1 had the leftmost digit 0. Then you go to the right and look for the leftmost digit for the second number. If it is greater than do no accept else move the head to the left most and start from the beginning. Also, when compared two bits just change them to * , so you know where to compare next.

The tape progression looks like this:

101<111

*01<*11

**1<**1

***<***

accept.

Using this simulator I have come up with the following code:

name: Accepting when num1<num2
init: s0
accept: sfin

//main program
s0,0
s1_0,a,>

s0,1
s1_1,a,>

//uncomment this to allow equality
//s0,<
//sfin,<,-

//s1_b means we read the leftmost symbol and it was b
s1_0,0
s1_0,0,>

s1_0,1
s1_0,1,>

s1_0,<
p0,<,>

s1_1,0
s1_1,0,>

s1_1,1
s1_1,1,>

s1_1,<
p1,<,>

//pb means the symbol read from the left number was b and we are looking for the digit from the right number
p0,b
p0,b,>

p1,b
p1,b,>

//COMPARISON LOGIC HERE

//if 0<0 continue exploring
p0,0
goleft,b,<

//if 0<1 immedaitely report yes
p0,1
sfin,b,-

//if 1<1 continue exploring
p1,1
goleft,b,<

//goleft state simply tells to go until reached a to start over
goleft,b
goleft,b,<

goleft,0
goleft,0,<

goleft,1
goleft,1,<

goleft,<
goleft,<,<

goleft,a
s0,a,>


This accepts only when the input tape has the true expression number1< number2 like

100100<100101

and it is limited to compare only the numbers of equal length (easy fix if needed to compare with different length, think about adding zeros to the first number until it matches the length of the second or reject if the length of the first number is greater).