<p>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.</p>

CC BY-SA 3.0
2012-02-14T15:52:12.953Z
I would like to have a formal proof.
malenkiy_scot
CC BY-SA 3.0
2012-02-14T15:49:01.943Z
2012-02-14T15:49:01.943Z
Janoma
<p>This question is an outgrowth of a certain maths problem I've been thinking about.</p>

<p>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 &lt; (k+1)/n$; but it can be any other oracle complying to the aforementioned rule).</p>

<p>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.</p>

<p>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?</p>

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

<p><em>Update:</em> 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.</p>

CC BY-SA 3.0
2012-02-14T16:14:33.433Z
It seems to me that you can use the oracle for equality to solve the halting problem.  Is this intended?
Tsuyoshi Ito
CC BY-SA 3.0
2012-02-14T16:15:42.003Z
@Tsuyoshi: No. Please elaborate.
malenkiy_scot
CC BY-SA 3.0
2012-02-14T16:20:11.617Z
Maybe I do not understand the question then.  What is the input to the equality oracle?  What do you mean by stating that it takes real-number oracles?  I thought that it takes the description of two Turing machines implementing the oracles, in which case it should be clear that it can be used to solve the halting problem.
Tsuyoshi Ito
CC BY-SA 3.0
2012-02-14T16:24:17.920Z
@Tsuyoshi: Turing machines cannot represent real numbers by a basic countability argument: the set of TMs is countable, the set of real numbers is not. You need something more 'powerful' than a TM. That's why it is called an 'oracle' - to underscore that it has some supra-computational powers. By the same token the equality oracle is just another way of saying that you have some 'supernatural' power to decide if two real-number oracles always produce the same result.
malenkiy_scot
CC BY-SA 3.0
2012-02-14T16:31:15.977Z
I thought oracles can be seen as "black boxes", so you wouldn't really have the description of a Turing machine *implementing* the oracles, right? Still, it seems unlikely that these black boxes can be used as input for another oracle, but even if we assume we can, the problem appears to be undecidable.
Janoma
CC BY-SA 3.0
2012-02-14T16:33:29.313Z
@Janoma, just for illustration: suppose that the equality oracle can produce and get the two answers to its first query in 1/2sec, second query in 1/4sec and so on. Then in 1sec it will have the answer.
malenkiy_scot
CC BY-SA 3.0
2012-02-14T16:40:03.407Z
@malenkiy_scot but you don't use time to define a computation. Still, oracles take constant time to answer, and it does not look like you understand how they are defined (even if you understand how they work). For example, what do you mean by "query", and how can oracles take infinitely many queries in finite time?
Janoma
CC BY-SA 3.0
2012-02-14T16:45:51.717Z
@Janoma, as I said, it was just by way of illustration. The decidability problem is that _given_ the oracles, is there a TM such that etc. I agree with your intuitive argument, but I do not think that it is sufficient on its own for the formal proof.
malenkiy_scot
CC BY-SA 3.0
2012-02-14T17:01:29.007Z
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)
Marzio De Biasi
CC BY-SA 3.0
2012-02-14T17:07:14.913Z
I'm not an expert, but if you pick $r = 1, p=0$, and $s$ is a *badly approximable* irrational number (i.e. exists a real $C(s)$ such that for every rational $\frac{u}{v}$ we have $| s - \frac{u}{v}| > \frac{C(s)}{v^2}$), then there is no way to decide if $s=q$ using your three "oracles".
Marzio De Biasi
CC BY-SA 3.0
2012-02-14T17:07:21.907Z
@Vor, good point. I was thinking just of comparing the original two numbers (and then it's enough to say 'suppose we can do it'), but we need more than that. I'll try to reformulate. Any suggestions?
malenkiy_scot
CC BY-SA 3.0
2012-02-14T17:14:23.750Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2012-02-14T17:17:18.267Z
@Tsuyoshi, you are right. See my reply above to Vor.
malenkiy_scot
CC BY-SA 3.0
2012-02-14T20:14:12.403Z
Are p and q part of the input to the problem, or are you trying to decide whether suitable p and q exist?  (I think your problem is undecidable either way.)
Jeffε
CC BY-SA 3.0
2012-02-14T20:24:30.080Z
@Je, Decide if they exist. What I want intuitively 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.
malenkiy_scot
CC BY-SA 3.0
2012-02-15T14:57:01.220Z
Closed at the request of the OP.
Dave Clarke
CC BY-SA 3.0
2012-02-15T18:09:07.453Z
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.
Kaveh
CC BY-SA 3.0
2012-02-15T19:23:01.197Z
@Kaveh: Thanks! Can you please refer me to introductory literature on the subject?
malenkiy_scot
CC BY-SA 3.0
2012-02-15T21:52:51.787Z
You can find some references [here](http://cstheory.stackexchange.com/questions/2119/the-reasons-for-bss-real-ram-model-being-prefered-in-computational-geometry). Also check [CCA](http://cca-net.de/).
Kaveh
<computability><oracles><computing-over-reals><computable-analysis>
Concerning decidability of a problem on real numbers
malenkiy_scot
# Concerning decidability of a problem on real numbers

(Asked by: username_0 on 2012-02-14)

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.

**Tags:** computability, oracles, computing-over-reals, computable-analysis
> **Comments:**
> **username_1**: It seems to me that you can use the oracle for equality to solve the halting problem.  Is this intended?  
> **username_0**: @Tsuyoshi: No. Please elaborate.  
> **username_1**: Maybe I do not understand the question then.  What is the input to the equality oracle?  What do you mean by stating that it takes real-number oracles?  I thought that it takes the description of two Turing machines implementing the oracles, in which case it should be clear that it can be used to solve the halting problem.  
> **username_0**: @Tsuyoshi: Turing machines cannot represent real numbers by a basic countability argument: the set of TMs is countable, the set of real numbers is not. You need something more 'powerful' than a TM. That's why it is called an 'oracle' - to underscore that it has some supra-computational powers. By the same token the equality oracle is just another way of saying that you have some 'supernatural' power to decide if two real-number oracles always produce the same result.  
> **username_2**: I thought oracles can be seen as "black boxes", so you wouldn't really have the description of a Turing machine *implementing* the oracles, right? Still, it seems unlikely that these black boxes can be used as input for another oracle, but even if we assume we can, the problem appears to be undecidable.  
> **username_0**: @Janoma, just for illustration: suppose that the equality oracle can produce and get the two answers to its first query in 1/2sec, second query in 1/4sec and so on. Then in 1sec it will have the answer.  
> **username_2**: @malenkiy_scot but you don't use time to define a computation. Still, oracles take constant time to answer, and it does not look like you understand how they are defined (even if you understand how they work). For example, what do you mean by "query", and how can oracles take infinitely many queries in finite time?  
> **username_0**: @Janoma, as I said, it was just by way of illustration. The decidability problem is that _given_ the oracles, is there a TM such that etc. I agree with your intuitive argument, but I do not think that it is sufficient on its own for the formal proof.  
> **username_3**: 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)  
> **username_3**: I'm not an expert, but if you pick $r = 1, p=0$, and $s$ is a *badly approximable* irrational number (i.e. exists a real $C(s)$ such that for every rational $\frac{u}{v}$ we have $| s - \frac{u}{v}| > \frac{C(s)}{v^2}$), then there is no way to decide if $s=q$ using your three "oracles".  
> **username_0**: @Vor, good point. I was thinking just of comparing the original two numbers (and then it's enough to say 'suppose we can do it'), but we need more than that. I'll try to reformulate. Any suggestions?  
> **username_1**: 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.  
> **username_0**: @Tsuyoshi, you are right. See my reply above to Vor.  
> **username_4**: Are p and q part of the input to the problem, or are you trying to decide whether suitable p and q exist?  (I think your problem is undecidable either way.)  
> **username_0**: @Je, Decide if they exist. What I want intuitively 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.  
> **username_5**: Closed at the request of the OP.  
> **username_6**: 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.  
> **username_0**: @Kaveh: Thanks! Can you please refer me to introductory literature on the subject?  
> **username_6**: You can find some references [here](http://cstheory.stackexchange.com/questions/2119/the-reasons-for-bss-real-ram-model-being-prefered-in-computational-geometry). Also check [CCA](http://cca-net.de/).  

---

## 1 answers

### Answer by username_2 on 2012-02-14. Score: 2

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.

> **Comments:**
> **username_0**: I would like to have a formal proof.  

---

