Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
1  
@Marc: Actually, I didn’t change the definition of the kind of Turing machine. The problem did: introduction of new symbols was explicitly allowed. (I’m aware of the theorems in question, but saw no need to go beyond the problem, since the OP is already struggling with that.) –  Brian M. Scott Jan 30 '13 at 8:03

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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