Real Analysis – Is Q the Orbit of a Continuous Function Computable on Q?

computability-theorycontinuityds.dynamical-systemsreal-analysis

In the previous post What is the smallest set of real continuous functions generating all rational numbers by iteration? I asked for the smallest set of continuous real functions that could generate $\mathbb Q$ by iteration starting from $0$. Surprisingly one continuous function suffices and this can also be Lipschitz and possibly analytic.

Given that we are applying the function only to rational numbers to generate our sequence the question arises whether it is possible that the function restricted to the rationals is also computable:

Is there a continuous function $f:\mathbb{R}\rightarrow \mathbb{R}$ that generates $\mathbb{Q}$ by iteration where $f$ restricted to $\mathbb{Q}$ is computable?

Best Answer

Yes. This answer is based on the answers to your previous question.

Start with a computable ergodic map $T$ (D. Thomine constructs an example here). For every basic open neighborhood $B_i$, the set $D_i = \bigcup_n T^{-n}(B_i)$ is a dense effectively open set, uniformly in $i$. So some computable real $p$ meets all the $D_i$, meaning $X = \{ T^n(p) : n \in \omega\}$ is dense.

There is a computable, order-preserving bijection $g: X \to \mathbb{Q}$ (back-and-forth argument), and we may assume that $g(p) = 0$. $g$ induces a (bi-computable) homeomorphism $G: \mathbb{R} \to \mathbb{R}$.

Define $f = G\circ T\circ G^{-1}$.


Constructing the bijection:

We'll build a computable sequence of rationals $(q_n)_{n \in \omega}$ and define $g(T^n(p)) = q_n$.

Begin with $q_0 = 0$. Then compute enough of $p$ and $T(p)$ to determine how they are ordered ($p < T(p)$ or $T(p) < p$). If $p < T(p)$, choose $q_1$ to be a rational greater than 0; otherwise, choose $q_1$ to be a rational less than 0. In either case, choose $q_1$ to be the appropriate rational with the smallest Gödel number.

Then compute enough of $p$, $T(p)$ and $T^2(p)$ to determine how they are ordered, and choose $q_2$ to be a rational in the same relative position to $q_0$ and $q_1$. Again, choose the appropriate rational of smallest Gödel number.

Etc.

This is all a computable process, so $g$ is computable. It's a total order-preserving injection by construction.

Surjectivity is by induction on Gödel number. For a rational $r$, by the inductive hypothesis all rationals of smaller Gödel number are in the range of $g$. So fix an $n$ such that all rationals of smaller Gödel number occur in $q_0, \dots, q_{n-1}$, and assume $r$ does not occur in this list, as otherwise we are done. Define $C = \{i < n : q_i < r\}$. By the density of $X$, there is an $m \ge n$ with $T^i(p) < T^m(p)$ for all $i \in C$, and $T^m(p) < T^i(p)$ for all $i < n$ with $i \not \in C$. Fix the least such $m$. Then by construction, $q_m = r$.

Related Question