2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Damnit, Alan Turing deserves a capital letter. $\endgroup$ – David Richerby Oct 28 '16 at 15:30
  • 1
    $\begingroup$ 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.) $\endgroup$ – David Richerby Oct 28 '16 at 15:33
  • $\begingroup$ 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. $\endgroup$ – Evil Oct 28 '16 at 17:19
2
$\begingroup$

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).

$\endgroup$
0
$\begingroup$

Think about it this way:

First of all replace the first 1 on the LHS and the RHS by a special character, say P.

Then start from the last character on the RHS,and move to the last character on the LHS. If the character on the left is the same as the one on the RHS, replace it by a symbol, say a. If it is less than, replace it by b and if it is greater than, replace it by c. Then do the same thing for the second to last character and so on until you reach P on the RHS.

So if you run the machine on 10100<10101 then you will get Paaab < PXXXX. Then all you need to check is that after P on the LHS you find at least one b, and there can be no c before it. For instance if checking 1101<1011 you get Pcba < PXXX will fail since there is a c before the b. Note here that as you proceed you change the last RHS character you read by an X to know it has already been checked

Also if you read a 0 or 1 in the LHS after P (LHS longer than RHS) like 100<10 or P0b < P0 it should also fail. And last of all if you are checking the kth character (from the end) on the RHS that is not P and the kth character on the LHS is a P, it means the RHS is longer than the LHS so it should accept.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.