Turing machine that computes if two integers are equal

Question

I am a philosophy student taking a Logic II class and I am scared. I have encountered the following question and I am bewildered about where to start or what to do.

Design a Turing machine to compute the following function: $$\text{equality}(x,y) = \begin{cases}1 \; \text{if} \; x=y \\ 0 \; \text{if} \; x \neq y \end{cases}$$ where $x,y \in \mathbb{Z}^{+}$. The machine need not be classical (you can write more than just 0 or 1 on the tape).

The scanner starts on the first digit of $x$, which is written in binary from left to right. After the binary expansion of $x$, there is a symbol $B$ representing a blank. After that, $y$ is written in its binary expansion. On either side of the entire expression there are infinitely many blanks.

Please help!

Answer 1

The basic idea is to have the machine scan back and forth, checking whether $x$ and $y$ have the same first symbol, the same second symbol, and so on. I’ll use one extra symbol, $2$.

• Step left and write a $2$.
• Go right until you encounter a blank.
• Go right until you encounter a blank, and write a $2$.
• Go left until you encounter a $2$, then step right. You are now at the first symbol of $x$, and the input is bounded between $2$’s.
• [LOOP] Change the first symbol of $x$ to $2$ and change state to show whether it was a $0$ or a $1$.
• Go right until you encounter a blank.
• Go right until you encounter a non-blank. If it fails to match the first symbol of $x$, return $0$. (Remember, you’re using the state to carry that information.) Otherwise, erase it.
• Scan back to the left until you encounter a $2$, then step right. You are at the first remaining symbol of $x$.
• If the current symbol is blank, $x$ is exhausted; go right until you encounter a non-blank symbol, return $1$ if that symbol is $2$ (meaning that $y$ is also exhausted), and return $0$ otherwise ($y$ was longer than $x$). If the current symbol is not blank, go back to [LOOP].

Try following this quasi-program with a small example or two to get the idea (and to catch any errors that I may have made), and then try to convert it into Turing machine code.

Answer 2

Just to show that you can apply the technique of Brian without introducing new characters, here's a sketch of a solution uning only $0$, $1$ and blank space.

• Perform a two-step to write a blank to the left of the current position and come back, just to make sure.

• While over a $0$ blank it and move to the right (erase leading digits $0$ from $x$, they should be ignored in equality testing).

• If now over a blank, go to the "test $y=0$" submachine.

• Move right until the second blank encountered, then one place to the left.

• [Main loop] (We are over the rightmost remaining digit of $y$.) Record current digit in the internal state and replace it by $0$; then move left until reaching a blank, then further left until reaching a non-blank.

• (We are over the rightmost remaining digit of $x$.) If the current digit differs from the one recorded in the internal state record inequality and terminate. Otherwise erase the current digit and move one to the left.

• If now over a blank, go to the "test $y=0$" submachine.

• Move right to the first non-blank, then further right to the next blank, then left, blank the digit (which was $0$) and go left.

• If now over a blank, record inequality and terminate; otherwise return to Main loop.

• [Test $y=0$ submachine] Move right until reaching a non-blank. While the current digit is $0$ move right. Now if over a blank record equality (write a $1$) otherwise recordinequality, and terminate in either case.

The "recording the digit in the internal state" means duplicating all internal states intil the test against the recorded digit (in the next step), with one copy for the case of a digit $0$, and another coy of the state for the digit $1$.