2

[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?

malenkiy_scot
  • 517
  • 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. – Thomas Andrews Feb 15 '12 at 13:45
  • @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$. – malenkiy_scot Feb 15 '12 at 14:05
  • 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? – Marc van Leeuwen Feb 15 '12 at 14:11
  • @Marc, obviously $q \neq 0$, otherwise the relation is not reflexive (you can't express $r$ via $s$). I'll edit it in. Thanks. – malenkiy_scot Feb 15 '12 at 14:24
  • @malenkiy_scot Another way of looking at it is to say that for any $x$ and any interval $[a,b)$ with $a<b$, 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. – Thomas Andrews Feb 15 '12 at 14:28
  • @Thomas, that's exactly how I understood it. Why didn't you post it as the answer, too trivial? – malenkiy_scot Feb 15 '12 at 14:35

1 Answers1

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.

malenkiy_scot
  • 517