Given a bounded decreasing sequence of rational number $a\_0,a\_1,\cdots$, then we know that it has limit $a$. Suppose this sequence satisfy that $|a\_k-a|<1/2^k$ for any $k$.


The sequence is given as an oracle: One can obtain $a\_k$ by querying $k$, and of course the limit $a$ is not known.


We are given another rational number $b$ and our goal is to decide whether $a=b$. Is this problem decidable?



Decide the limit of a decreasing sequence of real number
No, in the sense that if we had a decision procedure for this then it could also be used to decide the halting problem, for example.


For simplicity and without loss of generality, I will take $b = 0$. Then $a \neq 0$ corresponds to one of two $\Sigma^0\_1$-statements: $$(\exists k)(a\_k \leq 0) \quad\text{or}\quad (\exists k)(a\_k \geq 1/2^k).$$ Both of these are pretty generic so it's easy to reduce the halting problem to this.


Given a Turing machine $M$ (with blank input), consider the sequence $$a\_k = \begin{cases} \frac{1+17^{-k}}{2^{h+2}} & \text{$M$ halts in $h \lt k$ steps,} \cr \frac{1+17^{-k}}{2^{k+2}} & \text{otherwise.} \end{cases}$$ Then $M$ halts precisely when $\lim\_{k\to\infty} a\_k \neq 0$. 


