Turing Machine to compare multiple binary numbers

0
votes

I was wondering how to construct a Turing Machine for 

A<B<C<D...<N

with all numbers (A,B,C,D,...,N) being positive binary numbers.

These are a couple examples of how the machine should work:

1001 - Accepts because there is only one number

0<1 - Accepts

0010<1000<0001 - Doesn't accept because 1000!<0001

0100<1010<1010<1000 - Doesn't accept because 1010!<1010

I've tried methods that work to compare only two numbers but I can't seem to find a way to compare multiple (should work for infinite number of inputs) numbers.

1
binarycomparecomparisonturing-machines
Why do you need to compare more than two numbers? If A < B and B < C, then A < C. You should therefore only need to compare each consecutive pair of numbers until you reach the end of the input. - Welbog

1 Answers

0
votes

Here is a high-level block diagram for solving this problem. You can implement these blocks by using block feature of JFLAP.

High-level block diagram

Blocks Description
Done? : This block decides whether all comparisons are done, if yes, it accepts, otherwise, it goes to compare the very next two numbers.
A<B : This block is responsible to compare two binary numbers, the one that cursor is pointing at the first digit and the next one. You can use '<' as the separator between A and B and the next number.
cleanup: during the comparison, you might marked 0's and 1's to something else. This block clean up everything and prepare everything for the next comparison.

Hopefully, this gives you an idea to solve the problem.