0

My question basically boils down to “is there a minimum error bound to which almost all numbers can be computed to?” It’s possible that the definition I’m inventing here for rigor already exists, but googling got me nowhere.

For any $\epsilon > 0$, let a real number $x$ be called $\epsilon$-computable for some if there exists a real computable number $y$ such that $|x-y| \lt \epsilon$. For example, if $\epsilon = 0.1$, then we can show that $\pi$ is $0.1$-computable because $3.1$ is obviously computable and $|\pi-3.1| < 0.1$

It’s obvious that any computable number is $\epsilon$-computable for any positive $\epsilon$, but if $x$ is uncomputable, there may still be some minimum $\epsilon$ for which $x$ is $\epsilon$-computable. For example, the halting probability $\Omega$ is uncomputable, but is still $1$-computable because $0$ is computable and $|\Omega - 0| < 1$

Therefore, my question is this: is there some $\epsilon$ for which any given real number $x$ is almost always $\epsilon$-computable? What would define that tipping point?

Breaking Bioinformatics
  • 630

1 Answers1

4

Since every rational number is computable, the computable numbers are dense in $\mathbb R$, and so every real number is $\varepsilon$-computable for every $\varepsilon>0$.

On the other hand, for a given definition of a real number, there's no guarantee that you can write down an algorithm whose output you can prove approximates the target number to a particular percision.

For example, given any rational $\varepsilon>0$, you can pick a Gödel sentence $G$ for your favorite formal proof system and then define $$ x = \begin{cases} 0 & \text{if }G \\ 3\varepsilon & \text{if }\neg G \end{cases} $$ Then surely $x$ is close to some computable (indeed rational) number, but you can't ever prove that it will be approximated closer than $\varepsilon$ by any particular computation.

Troposphere
  • 7,158