I was wondering how you would go about making a two-tape Turing machine in linear time that starts with input 𝑥#𝑦 on Tape 1, where 𝑥 and 𝑦 are binary integers that might have leading 0's. It would accept the input if 𝑥 and 𝑦 have the same value such as 001101 has the same value as 1101. Would it be a good idea to replace the 1s and 0s with something like n and m to read the inputs and then if the turing machine gets to the # symbol it goes to the next binary string. Then if the n/m are the same it would accept the input and if they are different it would reject it? How would this be implemented?


1 Answer 1


Here is a sketch: Put the machine in a state where the first tape contains $x$ with no leading zeros, and the second tape contains $y$ with no leading zeros, then check that the contents of two tapes are equal.

To reach such state, assume that both $x$ an $y$ contain at least one $1$ (this can be easily checked). Then, scan the first (input) tape deleting all leading zeros. Continue scanning the tape without changing it until you find $\#$. Delete $\#$, then "move" $y$ to the second tape ignoring the leading zeros (write blanks on the first tape and the significant digits of $y$ to the second tape). Reset both heads to the first non-zero character of the respective tapes.

Interesting there exists no subquadratic Turing machine that solves your problem using only one tape.

Suppose such a Turing machine existed $T$, then you could use it to build the following Turing machine that decides the language $L$ containing all strings of the form $x' 2^n y'$ where $x',y' \in \{0,1\}^\ell$, $x'=y'$, and $\ell \ge 2$.

To do so you can:

  • Check that the string is of the form $\{0,1\}^*2^* \{0,1\}^*$ (if not, reject). This can be done in linear time.
  • Check that the string is of the form $\{0,1\}^\ell 2^\ell \{0,1\}^\ell$ with $\ell \ge 2$. This can be done in time $O(n \log n)$, where $n$ is the length of the input.
  • Prepend a $1$ to $x$
  • Replace all $2$s except the first and the last one with $0$.
  • Replace the first $2$ with $\#$ and the last $2$ with $1$.
  • Run $T$ on the current tape contents (which are now of the form $1x'\#00\dots 01y')$.

The overall time spent is $O(n \log n)$, where $n$ is the length of the input. However $L$ cannot be decided by any Turing machine with running time $o(n^2)$. See pages 566-569 of One-Tape, Off-Line Turing Machine Computations.

  • $\begingroup$ Good analysis. However: the question mentions two tapes, for which the problem becomes much simpler. $\endgroup$ Nov 13, 2023 at 10:47
  • 1
    $\begingroup$ @HendrikJan, agreed. The first part of my answer addresses two-tape Turing machines. I went on a tangent researching the problem for single-tape Turing machines (because I had originally misread the question) and I thought I'd also discuss that case. $\endgroup$
    – Steven
    Nov 13, 2023 at 10:49
  • 1
    $\begingroup$ My bad! I should actually read the full answer before commenting. $\endgroup$ Nov 13, 2023 at 10:51

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.