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.
