In the proposed example, the TM M computes proper subtraction:
m∸n=max(m−n,0)On the tape, the initial input is
0m10nthat is m zeros, a separator 1, and n zeros.
The final output is:
0max(m−n,0)therefore:
-
if m≥n → m−n zeros remain on the tape
-
if m<n → 0 zeros remain on the tape (blanks only)
My doubt lies in the fact that if m>n, the first zero of the sequence 0^m is always overwritten with B, and this implies that [(m−1)−n] zeros remain on the tape instead of [(m−n)], as required by the exercise. This happens because the search starts with the leftmost zero of the sequence 0^m and subsequently the leftmost zero of the sequence 0^n.
To avoid this problem, I thought that the search procedure could be inverted by first searching for the leftmost zero of the sequence 0^n and then for the leftmost zero of the sequence 0^m.
I remain available for any questions and trust that someone can help me understand the correct interpretation, should mine be incorrect.
