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.

Improve this question
$\endgroup$
19
  • $\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, 2012 at 16:14
  • $\begingroup$ @Tsuyoshi: No. Please elaborate. $\endgroup$
    – malenkiy_scot
    Feb 14, 2012 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, 2012 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, 2012 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, 2012 at 18:09

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I would like to have a formal proof. $\endgroup$
    – malenkiy_scot
    Feb 14, 2012 at 15:52

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