5
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ As a rule of thumb, any concrete continuous function is going to be computable, unless it was built to be non-computable. $\endgroup$
    – Arno
    Commented Jan 31, 2022 at 12:28

1 Answer 1

6
$\begingroup$

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$.

$\endgroup$
7
  • $\begingroup$ Hi Dan thank you for your answer very much appreciated! I have a question which is I'm not sure I quite understand how the computable, order preserving bijection works. I know that you can form a bijection between X and $\mathbb{Q}$ as they are both countable sets but how do you make it computable and order preserving? $\endgroup$
    – Ivan Meir
    Commented Jan 31, 2022 at 12:46
  • 2
    $\begingroup$ @IvanMeir I'll edit in a bit more detail. $\endgroup$ Commented Jan 31, 2022 at 20:27
  • 1
    $\begingroup$ In case it helps, this wikipedia article has another explanation of how the back and forth method works (in the "Application to densely ordered sets" section) $\endgroup$
    – Saúl RM
    Commented Jan 31, 2022 at 21:17
  • $\begingroup$ @DanTuretsky Thanks Dan that makes sense now - a satisfying argument and good to learn about. One further detail I'd like to clarify is the existence of the real number $p$ based on the assumption that $T$ is computable and ergodic. Would you be able explain this further? Also are we able from the $T$ defined by D Thomine to calculate $p$ in reality or are you just asserting the existence of a real number $p$ that is itself computable? $\endgroup$
    – Ivan Meir
    Commented Feb 1, 2022 at 14:07
  • 1
    $\begingroup$ @IvanMeir Yes, we can calculate $p$. Choose an interval $I_0$ of length at most 1 contained in $D_0$. Then choose an interval $I_1$ of length at most $1/2$ contained in $D_1 \cap I_0$. In general, choose an interval $I_{n+1}$ of length at most $2^{-(n+1)}$ contained in $D_{n+1}\cap I_n$. $p$ is the unique element of $\bigcap_n I_n$. For that particular $T$, finding such intervals should be straightforward. $\endgroup$ Commented Feb 1, 2022 at 22:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .