2
$\begingroup$

Prove that set of rational numbers less than given computable real number is decidable

This problem was in my exam yesterday, but I was not able to solve it. However I still want to give it another try.

Same problem can be stated in this way:
Construct an algorithm, which answers the question: Is our given rational number less or greater than their(fixed) computable number?

Here's my poor try so far.

Since it's analysis related problem, I used the $\epsilon - \delta$ definition of computable number, which is:

$\exists f$ computable function, such that $\forall \epsilon > 0, \epsilon \in \mathbb{Q}, f$ gives us $\delta > 0, \delta \in \mathbb{Q}$ such that$|a - \delta| \leq \epsilon$ holds for given computable number $a$

Let $p \in \mathbb{Q}$ be our input, and let $f$ compute for us 2 rationals $q_1$ and $q_2$. It is well known that $|q_1 - q_2| < 2\epsilon$

Now let's choose $\epsilon = \frac{1}{2^{i}}, i = 0,1,2,...$
For each $i$-th step I compute $f$ twice and get $q_{i_{1}},q_{i_{2}}$. I think that our given rational $p$ should hold some condition with both $q_{i_1},q_{i_2}$ which will help me to finish the algorithm, but I couldn't figure this out. I believe there are finitely many checks for each step which will let me know that for example $p < a$ just like in picture below.

enter image description here

What do you think about this problem? Maybe there's more straightforward way to prove this. Thank you.

$\endgroup$
  • $\begingroup$ It isn't decidable whether a given computable number is non-negative or not (even Wikipedia knows that!), so I don't think that what the question is asking is actually possible. $\endgroup$ – Yuval Filmus Jan 25 '17 at 21:24
  • $\begingroup$ hmm.. similar problem comes from my textbook, but uses number $e$ instead of arbitrary computable number, is it change something? $\endgroup$ – shcolf Jan 25 '17 at 21:29
  • $\begingroup$ @YuvalFilmus But here the computable real number is fixed, and we are given a rational number to check. We don't need a uniform solution on the real. We only need to prove that for any comp. real we have an algorithm working on rationals. $\endgroup$ – chi Jan 25 '17 at 21:30
  • $\begingroup$ You can solve it for $e$ since it's given as the limit of a rational series with vanishing bounds on the tail, but you can't solve it in general. $\endgroup$ – Yuval Filmus Jan 25 '17 at 21:32
  • $\begingroup$ can't we construct a Cauchy sequence for it just by using the above definition? $\endgroup$ – shcolf Jan 25 '17 at 21:35
3
$\begingroup$

I would approach this problem as follows. Let $a$ be the computable real, and $A = \{x\in\mathbb{Q}\ |\ x<a\}$.

If $a \in \mathbb{Q}$, then $A$ is decidable since $x<a$ is a comparison between rationals, which is decidable.

Otherwise, we can assume $a$ is irrational. Our algorithm performs the following. First, we take the candidate $x\in\mathbb{Q}$ as input. We then query $f$ (the function which approximates $a$ as requested) repeatedly with $q=2^{-n}$ for every $n>0$. Eventually, for some $n$ we will obtain one of

$$ f(2^{-n}) + 2^{-n} < x \qquad \lor\qquad x < f(2^{-n}) - 2^{-n} $$ Indeed, this will happen as soon as $2^{-n} < |x-a| / 2$, which is a possibility because we know $x \neq a$.

In the first case, we return $x > a$ ($x \notin A$), in the second we return $x<a$ ($x \in A$).

The correctness comes from $$ a \leq f(2^{-n}) + 2^{-n} \qquad \land\qquad f(2^{-n}) - 2^{-n} \leq a $$ being true for all $n$.


Note that this solution is not uniform in $a$. That is, we only prove that there is an algorithm for any computable $a$, taking a candidate rational $x$ as input. We do not show that there is a single algorithm that, given both $a$ and $x$ as input is able to decide $<$ (indeed, that would be undecidable).

$\endgroup$
  • $\begingroup$ How does the algorithm check that $a \in \mathbb{Q}$? $\endgroup$ – Craig Gidney Jan 25 '17 at 22:38
  • $\begingroup$ @CraigGidney It does not (and can not). This is covered by the very last comment on the non-uniformity of the solution. We only prove that for any $a$ there is an algorithm: for this it is enough to choose one algorithm for rational $a$, and another one for irrational $a$. $\endgroup$ – chi Jan 25 '17 at 23:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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