Suppose algorithm $A$ on a digital computer takes as input integers $x$ and $y$ in binary. The algorithm outputs one if $x=y$, and zero if $x \neq y$. Is there a proof that for any input $x$ and $y$ in which $x=y$, there exists a one-to-one function $f: \mathbb Z \rightarrow \mathbb Z$ such that $A$ compares all of the bits of $f(x)$ to all of the bits of $f(y)$?

  • 1
    $\begingroup$ Suppose $A$ doesn't look at some bits of $f(x)$ or $f(y)$. Is $A$ still correct for every input? $\endgroup$ – Discrete lizard Dec 12 '17 at 17:18
  • 5
    $\begingroup$ I'm not clear what role f is here. When if f fixed? It's not clear if you are asking if there is some function f which will require that all bits are looked at, or something different. if f(x) = 2x, then it is one-to-one and it just appends a 0 to the end of x and y every time, so that last bit doesn't need to be looked at. But if f(x)=x, then surely you must look at all bits. Is f(x) supposed to a compression function? or perhaps is a function that adds redundancy, like in error correcting/detecting codes, in which case some redundant bits can be ignored. You need to clarify the role of f. $\endgroup$ – JimN Dec 12 '17 at 18:46
  • 2
    $\begingroup$ Try formulating your claim formally. That's the first step toward proving it. The answer also could depend on the exact model of computation. $\endgroup$ – Yuval Filmus Dec 12 '17 at 18:52
  • 3
    $\begingroup$ As the problem us stated, the obvious answer is no: an algorithm receiving x and y as the input an only look at x and y, no bits of f(x) are visible to it unless f is trivial. Please reformulate the question so that the role of f becomes explicit. $\endgroup$ – jmster Dec 14 '17 at 18:31
  • 2
    $\begingroup$ Please edit the question to clarify it. The quantifiers are not clear to me. Do you mean "there exists $f$ such that every correct algorithm must look at all the bits of .."? Or do you mean "For all $f$ every correct algorithm must look at the bits of...?" Or "for every correct algorithm there exists $f$ such that the algorithm looks at all the bits of..."? It's hard to answer the question if it's not clear what the question is asking. $\endgroup$ – D.W. Dec 14 '17 at 18:41

There is a problem with your question because it is ill-posed.

First, in your question you talk about a function $f$ as if a Turing machine somehow operates with functions and can "use" such an $f$ during its execution. This is not the case. A Turing machine operates with tapes and heads, and it has states, and a transition function. So you need to carefully explain what it means for the machine to "compare bits of $f(x)$ and $f(y)$". Do you claim that the machine will write down $f(x)$ and $f(y)$ onto a tape at some point? What if it encodes the least significant bit of $f(x)$ and $f(y)$ in its state, and it writes down the rest onto a tape?

Second, there is no instruction corresponding to "compare bits". Even if we add one to the Turing machine, the machine can avoid using it and still effectively compare bits. It is also possible to compare bits in ways that are not easily recognizable as such. So the whole notion of "compare bits" is ill-formed, at least for the traditional notion of Turing machine.

It is possible to make your question precise in several ways. For example, we could devise a "comparison network" that consisted of wires and equality tests, much like the sorting networks use comparisons. Then we could ask about the structure of a comparison network that correectly compares numbers.

Another way to make your question precise is to avoid talking about "comparison of bits", and instead ask whether the machine reads bits. This is not a problematic concept because we know what it means: the machine reads a bit if at any point in the execution of the algorithm the head scans the cell that contains the bit.

Now, to answer your question, let us make the conditions of the problem precise. Let us say that the two numbers in question $x$ and $y$ are written on two read-only tapes $t_x$ and $t_y$. Suppose we have a Turing machine $T$ which writes $0$ on the output tape if $x \neq y$ and it writes $1$ if $x = y$.

Theorem: If $T$ outputs $1$ then during its execution it scans every bit on $t_x$ and every bit on $t_y$.

Proof. We prove the statement by contradiction. Suppose there were a bit of $t_x$ which was not scanned (the argument is symmetric if there is an unscanned bit of $t_y$). Then the machine would operate in exactly the same way if we flipped that bit. Because we assumed that the machine works correctly, this would imply that the machine outputs $1$ on input $x$, $y$, and also on input $x'$, $y$ where $x'$ is $x$ with one bit flipped. It would follow that $x = y = x'$, a contradiction. QED.

  • $\begingroup$ I wasn't expecting nor did I want an answer like this, but I can't argue with it; it is correct. $\endgroup$ – Craig Feinstein Dec 19 '17 at 16:28
  • 1
    $\begingroup$ I disagree with this answer. In fact, the question is valid and somewhat interesting (albeit it needs more details about the computational model). It is trivial to show that the machine scans every bit of the input for almost any interesting problem (including this one). However, in this case, whenever the machine accepts, the bit comparisons it has done need not be among $x,y$ themselves, but one can show they must be among some $x', y'$ that are computed from $x, y$ as described by some injective $f$ (injectivity suggests you cannot do better than linear comparisons, not just steps). $\endgroup$ – Omar Dec 20 '17 at 5:49
  • $\begingroup$ @Omar: you are always free to write your own answer. If you do, please explain carefully (without waving hands) what it means for a Turing machine to "compare bits". In your comment you use this notion without explaining it, nor is it explained anywhere else here. As far as the triviality of the anwer goes: that's what the question required. $\endgroup$ – Andrej Bauer Dec 20 '17 at 8:46
  • $\begingroup$ @Omar, I gave Andrej the bounty, but if you give your own answer and it is also correct, I'll give it a thumbs up. $\endgroup$ – Craig Feinstein Dec 20 '17 at 15:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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