Pergunta

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.

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top