I was wondering if there is any research in the field of Diophantine Approximation using the computable numbers. It seems to be a good fit, a dense countable set with a variety of different potential height functions.

The basic premise of Diophantine approximation is that you take a dense countable set(traditionally the rationals or the algebraic numbers), $A$ in some range(generally $(0,1)$) and a function $H: A \to \mathbb N$, the height function. You then see how given $N \in \mathbb N$ close you can get a member of $A$, usually referred to as $\alpha$ with $H(\alpha) < N$. The most famous result from this field is Dirichlet's Approximation Theorem which states that for any real in $(0,1)$ there exist infinitely many rationals $\frac{p}{q}$ such that $|x-\frac{p}{q}| \le \frac{1}{q^2}$. This has been shown to be optimal up to a constant.

Some height functions I imagined for the computable numbers would be

1) $H_c(\alpha)$ This is a restricted version of the above when the Turing machine is restricted to having $c$-characters not counting blank.

2) Same as 1 just counting transitions instead of states.

3) Some function on the time complexity to generate the number

4) Some function on the space complexity to generate the number

The first 2 are basically variants on Kolmogorov complexity I believe. The last two I'm not even sure how to map to the Naturals.

Here are some preliminary results I believe are true.

For 1 Using just rationals and an $x \in (0,1)$ you get an approximation of the following form $$|x-\alpha| \le Cc^{-H_c(\alpha)}$$ For some $C>0$. I believe I can prove this. If it is true that using algebraic numbers of degree at most $d$ gives an approximation function of $|x-\alpha| \le cH^{-d-1}(\alpha)$ for some $c>0$ then I believe the same approximation function holds even if you use all algebraic numbers. The basic reasoning behind this is that it takes $O((d+1)\log_c(\max(a_1,\dots,a_{d+1})))$ states to output all the coefficients to the tape and then you should be able to do Newton's algorithm with a constant number of states. In the last equation $a_1,\dots,a_{d+1}$ is the set of coefficients of the minimal polynomial specifying $\alpha$.

Noting that the number of transitions is approximately equal to $c+1$ times the number of states you get an equivalent statement for 2 that for $x \in (0,1)$ you get $$|x-\alpha| \le Cc^\frac{-H_c(\alpha)}{c+1}$$

For some constant $C > 0$. Due to these results I'd say 2 is probably the nicest approximation function since $c^\frac{n}{c+1}$ when restricted to integer inputs is bounded by $\sqrt[5]{4}^n$ or roughly $1.3195^n$.

A result I'd like to have and I believe is true is that the bounds on the approximation function for $3$ are optimal, that is that there exists $x \in (0,1)$ such that $$|x-\alpha| \ge Cc^\frac{-H_c(\alpha)}{c+1}$$ For some constant $C>0$ and all but finitely many computable $\alpha$.

This is a cross-post from math.stackexchange. It was suggested to me that this site would be more likely to answer my question if there is any research or if this is worth pursuing any farther.

  • $\begingroup$ It's not clear to me what preciely you're asking here. Is there any reseearch? Well, did you check the usual places, like MathSciNet? If you can prove these results, you could present them to the relevant communities and see what they say (for instance Computability in Europe and Computability and Complexity in Analysis would be two conferences where the topic would be deemed relevant). $\endgroup$ May 14, 2015 at 7:10
  • $\begingroup$ @AndrejBauer I did check and couldn't find anything. I just wasn't sure if maybe people used different terms for the same thing in computer science. I'll look into firming up the proofs and presenting them if no one answers here on there being any research. $\endgroup$
    – ruler501
    May 14, 2015 at 11:40
  • $\begingroup$ There's definitely research in "how computable" a real number is (for instance, maybe we can only approximate it computably from below), and there is definitely a notion of computational complexity for real numbers. But your complexity looks more like Kolmogorov complexity, and I have not really heard of anything like that (but it's not my area either). $\endgroup$ May 15, 2015 at 7:45
  • $\begingroup$ @AndrejBauer The approximations I'm working with aren't computable. Mainly meaning you can't determine what the best approximation of the number is computably. The difference between my idea and Kolmogorov complexity is that transitions can specify approximately $(3n)^n$ different machines while Kolmogorov is $a^n$, where $a$ is the size of the alphabet $\endgroup$
    – ruler501
    May 15, 2015 at 15:40

1 Answer 1


It's funny you should ask, because computability and diophantine approximation has actually been a popular topic in recent years. In particular Becher and Slaman and coauthors have many results and papers. See for instance

Becher, Verónica; Reimann, Jan; Slaman, Theodore A., Irrationality exponent, Hausdorff dimension and effectivization, ZBL06837203.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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