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.
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
YYXYY11X notice that the left operand is zero
Y111XX notice that the right operand is zero
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:
YYYYY11XYYYYX notice that the right operand is zero
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.