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: enter image description here

  • $\begingroup$ I do not follow your first example - can you please check it? $\endgroup$
    – greybeard
    Dec 15, 2020 at 9:46
  • $\begingroup$ @greybeard I think the results is zero whenever the second operand is greater than the first one $\endgroup$
    – melfnt
    Dec 15, 2020 at 10:15
  • 1
    $\begingroup$ (@melfnt I had noticed you implied this in your answer. I'm not contradicting it. I do not find the first example in this question helpful as is: without mention how to interpret/handle more $1$s after the first $X$ than before.) $\endgroup$
    – greybeard
    Dec 15, 2020 at 10:19
  • $\begingroup$ @greybeard sure, whatever. Let's wait and see if OP clarifies: I will edit my answer if needed $\endgroup$
    – melfnt
    Dec 15, 2020 at 10:22

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

  • $\begingroup$ I do understand your examples, but I don't know how I can translate that into my code (turingmachine.io format). Do I make my ones into Y in of my states? $\endgroup$
    – TalionZz
    Dec 15, 2020 at 9:16
  • $\begingroup$ @TalionZz I'll update my answer but I can't write the whole program for you otherwise you won't learn the turing machine -- I suppose this is a homework, right? $\endgroup$
    – melfnt
    Dec 15, 2020 at 9:29
  • $\begingroup$ it is an optional exercise that my teacher recommended, it isn't a due assignment. I just thought that knowing how to do it would be better for me. $\endgroup$
    – TalionZz
    Dec 15, 2020 at 9:33
  • 1
    $\begingroup$ @TalionZz sure it will, but you have to think by yourself otherwise you won't learn. I think you should start over with your program: I added a sketch of the algorthm, try and translate it into your language. The cleanup phase is an exercise (: $\endgroup$
    – melfnt
    Dec 15, 2020 at 9:46
  • 1
    $\begingroup$ @TalionZz I see the problem but I won't tell you what is it, you have to do it by yourself. Run the machine step-by-step and be careful to spot when it behaves differently from what you would expect: the last used rule is wrong. Notice (1) the state in which the machine is and (2) the current cell. If the first is wrong, you have to fix the next-state part of the last used rule, if the latter is wrong you have to fix the direction part of the last used rule $\endgroup$
    – melfnt
    Dec 15, 2020 at 14:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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