How can I do a subtraction on unary numbers terminated in X on turing machine?

Question

For example, if I have 11X1111X as input, the result should be X. For another example, input: 1111XX -> 1111X. I am a complete beginner and all my tries so far failed to meet the expectation.

This was my latest try:

Answer 1

First of all, notice that if you have to compute $N-M$ you can subtract one from each operand and the result will not change (i.e. $N-M = (N-1) - (M-1)$.

Keeping that in mind, I would remove a 1 from each operand replacing it with another symbol Y just to avoid spaces on the tape, and repeat until either operand "runs out" of ones --that means that either $N$ or $M$ is now zero. When it happens, clean out the tape a little bit: the left operand is the result of the computation.

So, executing this algorithm in your examples: example 1

11X1111X input
Y1XY111X
YYXYY11X notice that the left operand is zero
  X      cleanup

example 2

1111XX input
Y111XX notice that the right operand is zero
1111X  cleanup

As you can see from the second example, if the first operand is bigger than the second you will have to revert the last substitution replacing a Y with a 1.

Another meaningful example:

1111111X1111X input
Y111111XY111X
YY11111XYY11X
YYY1111XYYY1X
YYYY111XYYYYX
YYYYY11XYYYYX notice that the right operand is zero
    111X      cleanup

As for the actual program, here is just a sketch, try to write it yourself:

• in q0 search for a 1 to replace. That means, skip all the Ys and continue moving right until you find a 1, then don't move and go to q1.
• in q1 replace the 1 with a Y, then move right and go in another state (q2) to reach the other operand.
• in q2, go right until you find an X (that means you have reach the second operand), then move right and go to q0 to remove a 1 from the second operand too.

This part will replace a 1 from both operands (if there are enough ones), the states of the machines are q0 -> q1 -> q2 -> q0 -> q1 -> q2.

At this point the scanner is placed at the end of the input string, you realize it when you find an empty cell in q2, so;

• in q2, if you find an empty cell, move left and go to q3 (which will move the scanner at the beginning of the input).
• in q3 move left ignoring any character until you find an empty cell. That means you have reached the beginning of the string. Move right and go to q0.

This loop continues until either operand runs out of 1s. You realize it when you find an X in q0, so:

• in q0 if you find an X, move right and go to q4 that is the state that initializes the cleanup part
• in q4 move right ignoring any character until you find an empty cell, that means you have reached end of the input, move left and go to q5 to perform the cleanup phase.

Complete the program as an exercise: if you want you can edit this answer to add the sketch of the cleanup phase.