Constructing a Turing Machine for the min function

[trash]

Homework Statement

I'm trying to construct a Turing machine that after receiving two integers $x,y$ gives back the smaller one (or any of them if they are equal).

Homework Equations

I cannot use anything besides zeros and ones (I have seen that some people make turing machine using letters to keep track of the cursor). The infinite tape has only zeros, the inputs $x,y$ are given by the same quantity of 1's separated by a zero.
Example: A input for $min(x,y)$ with $x=4,y=3$ would be $\dots 00011110111000\dots$ with infinite zeros on both sides of the tape.

The result here would be $\dots 0001111000\dots$ with the cursor in the first one (standard position). This string can appear anywhere, there is no need for the former entries to be deleted.

The Attempt at a Solution

I haven't found a way to develop a proper algoithm to do what I want. My main idea was first copy both inputs, then in the copy take a [itex]1[itex] from the second input, take it to first non-zero entry of the first input in the copy and make it zero. If the second input is bigger than the first one the cursor will hit a [itex]1[itex] and the zero separating the inputs, otherwise it will hit a zero. In the first case I would return the cursor standard position of the original first input, in the second case the first entry is bigger or equal to the second one so I can move to the standard position of the second input.

That's the my idea, but I have some problems to give a model since dealing with the copy machines and then going back to the original inputs is something I have some problems to figure out the way to do it.

 

[mighty2000]

Hello,

Thank you for sharing your ideas for constructing a Turing machine that finds the smaller of two integers. I think your approach is a good start and can definitely be refined to achieve the desired result.

One suggestion I have is to use a temporary "working" tape to store the copied inputs, instead of trying to go back and forth between the original and copied tapes. This can simplify the algorithm and make it easier to keep track of the cursor position.

Here is a possible algorithm for your Turing machine:

1. Start at the standard position of the first input tape.
2. Copy the first input to the working tape, leaving the original input tape unchanged.
3. Move the cursor to the standard position of the second input tape.
4. Copy the second input to the working tape, leaving the original input tape unchanged.
5. Move the cursor back to the standard position of the first input tape.
6. Compare the first two symbols on the working tape. If they are both 1, move the cursor to the next symbol on the working tape and repeat this step until one of the symbols is a 0.
7. If the symbol on the working tape is a 0, move the cursor back to the standard position of the first input tape and return the cursor to the standard position of the original first input tape.
8. If the symbol on the working tape is a 1, move the cursor back to the standard position of the second input tape and return the cursor to the standard position of the original second input tape.

This algorithm essentially compares the two inputs symbol by symbol and returns the cursor to the smaller input. If the inputs are equal, it will return the cursor to the standard position of either input.

I hope this helps and good luck with your Turing machine!