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
    Given a finite set of inputs, you've narrowed the value of $r$ to some interval, $[a,b)$. Now just show that, given two non-empty intervals $[a,b)$ and $[c,d)$ there must by a $r_1\in[a,b)$ and $r_2\in[c,d)$ that are such that $r_1\neq_Q r_2$. So the finite number of steps hasn't restricted your real number enough.2012-02-15
  • 0
    @Thomas, what you mean, I think, is that $[a,b)$ must contain $r'$ such that $s =_Q r'$. Then $r'$ will produce the exact same sequence of outputs as $r$.2012-02-15
  • 0
    Your relation is not an equivalence relation (every rational $s$ is related to every real $r$ (taking $q=0$) but not symemtrically). The closest thing I can see that is an equivalence relation is that the images in the rational vector space $\mathbb R/\mathbb Q$ of $r,s$ are related by a nonzero rational factor. Is that what you meant, or something different?2012-02-15
  • 0
    @Marc, obviously $q \neq 0$, otherwise the relation is not reflexive (you can't express $r$ via $s$). I'll edit it in. Thanks.2012-02-15
  • 0
    @malenkiy_scot Another way of looking at it is to say that for any $x$ and any interval $[a,b)$ with $a, there is an $x'=_Q x$ for some $x'\in [a,b)$. So, no matter how many finite steps of $r$ you take, you have not narrowed down its equivalence class under $=_Q$ at all - it could be a member of any of the equivalence classes.2012-02-15
  • 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.