2
$\begingroup$

[This is a cleaner and simpler restatement of a question I asked earlier on Theoretical CS forum. Please re-tag as appropriate.]

Suppose you have two oracles (black boxes) that represent real numbers. Each oracle works like this: you give it integer $n$ and it returns integer $k$ such that $k/n \leq r < (k+1)/n$, where $r$ is the real number the oracle represents.

Suppose Bob knows the numbers and wants to prove to Alice that they are different. He then may produce input $n$ such that the oracles return different answers.

Now consider the equivalence relation $s =_Q r \Leftrightarrow \exists q,p \in \mathbb{Q}, q \neq 0$ such that $s = qr + p$, (where $\mathbb{Q}$ is the set of rational numbers).

Can Bob prove to Alice that $s \neq_Q r$ in a finite number of steps using only finite inputs? I think he can't, but how do you prove it?

  • 0
    @Thomas, that's exactly how I understood it. Why didn't you post it as the answer, too trivial?2012-02-15

1 Answers 1

3

The answer turns out to be rather trivial (Thomas, thanks for pointing me in the right direction):

After a finite sequence of queries proving that $s \neq_Q r$ the possible value of $r$ is restricted to an interval $[a,b)$. That interval will necessarily contain some r' such that r' =_Q s. But the oracle for r' would produce the exact same sequence of answers as the oracle for $r$. Contradiction.