1
$\begingroup$

This question is an outgrowth of a certain maths problem I've been thinking about.

Suppose you use an oracle to represent a real number. The oracle is of the following form: you give it an integer and it returns you an integer back (for example: given input $n$ the oracle representing $r$ returns integer $k$ such that $k/n \leq r < (k+1)/n$; but it can be any other oracle complying to the aforementioned rule).

Now, given two oracles like that you can't decide if they represent equivalent numbers (if the numbers are equal the algorithm won't halt in 'most' cases). So you are given another oracle that takes two real-number oracles as input and tells if they represent equal numbers.

Given two real numbers $r$ and $s$ represented by such oracles plus the oracle that tells us if two real numbers are equal is it possible to decide if $s = qr + p$, where $q$ and $p$ are rational?

Please provide a formal proof (or at least an idea that can be easily formalized into a proof).

Update: There is a problem with the oracle comparing two real numbers - see comments. Intuitively what I want is the answer to the following question: is deciding that two real numbers belong to the equivalence class defined by $s=qr+p$ harder than deciding if they are equal. I'll close this question and restate it.

$\endgroup$

closed as not a real question by Tsuyoshi Ito, Dave Clarke Feb 15 '12 at 14:57

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ It seems to me that you can use the oracle for equality to solve the halting problem. Is this intended? $\endgroup$ – Tsuyoshi Ito Feb 14 '12 at 16:14
  • $\begingroup$ @Tsuyoshi: No. Please elaborate. $\endgroup$ – malenkiy_scot Feb 14 '12 at 16:15
  • 1
    $\begingroup$ Suppose that the two oracles for $r$ and $s$ are given, how do you use the third comparison oracle? (you cannot feed it from a TM because the "real number oracles" are uncountable) $\endgroup$ – Marzio De Biasi Feb 14 '12 at 17:01
  • 1
    $\begingroup$ I think that you have misunderstood my question. Let me ask again: What is the input to the equality oracle? My guess is still that the input is two Turing machines (note that these Turing machines can invoke other oracles, so your counting argument does not apply), but even if my guess is wrong, you should have some answer to the question. In short, your question is underspecified. $\endgroup$ – Tsuyoshi Ito Feb 14 '12 at 17:14
  • 2
    $\begingroup$ There are models of real-computation where deciding equality between real numbers is permitted, e.g. BSS/real-RAM model. But you should be careful about choosing the right model, different models will lead to different answers. It seems to me that what you want to know is whether "deciding" linear independence of two given real numbers over the rational field is harder than "deciding" the equality between real numbers. And as I said the answer will depend on the model. I suggest that you first think about the simpler question that a given real number is rational or not. $\endgroup$ – Kaveh Feb 15 '12 at 18:09
2
$\begingroup$

I think it's undecidable, but I don't have a proof. Intuitively, if $s\neq qr+p$ for all $p,q\in\mathbb{Q}$ (i.e. if the answer is "NO"), then you will be always looking for a "next" pair $(q,p)$ such that $|s-(qr+p)|$ is smaller than before. You don't really have an argument to decide when to stop and return "NO" because, for all you know, there is a better approximation to $s$ of the form $qr+p$ than the one you already have.

$\endgroup$
  • $\begingroup$ I would like to have a formal proof. $\endgroup$ – malenkiy_scot Feb 14 '12 at 15:52

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