TITLE: Is there a primitive recursive real number which cannot have a primitive recursive expansion?
QUESTION [5 upvotes]: Using the definitions given below, my question can be restated as

Does there exist a primitive recursive (PR) real $\{s_n\}$ such that for every scale $r \geq 2$ and every PR sequence $a_n$ with $0 \leq a_{n+1} \leq r-1$ it is NOT the case that 
  $$
\{s_n\} = \{ \sum_{p \leq n} a_p r^{-p} \}
$$

If $\{s_n\}$ is a PR real number and if $a_n$ is a PR sequence such that
$$
0 \leq a_{n+1} \leq r-1, r \geq 2
$$
and
$$
\{s_n\} = \{ \sum_{p \leq n} a_p r^{-p} \}
$$
then $\{s_n\}$ is said to have the PR expansion $\sum_{p \leq n} a_p r^{-p}$ in the scale of $r$.
A rational PR function which is PR convergent is called a PR real number.
PR real numbers $\{s_n\}$ and $\{t_n\}$ are equal, denoted $\{s_n\} = \{t_n\}$,  if $\vert s_n - t_n \vert < 1/10^k$ for majorant $n$.
A rational PR function $f(x)$ is PR convergent if there is a PR $N(k)$ such that $N(k+1) \geq N(k) \geq k$ and
$$
i,j \geq N(k) \rightarrow
\vert f(i)-f(j) \vert < 1/10^k
$$

REPLY [4 votes]: I think it's useful to first consider an analogous situation in constructive mathematics. It is not possible to show constructively that every real number has a base $b$ expansion. This is because if the expansion starts $0.xxxx$, then we know the number is less than or equal to $1$, and if the expansion starts $1.xxxx$ we know the number is greater than or equal to $1$. But to be able to decide whether a number is $\leq 1$ or $\geq 1$ is equivalent to the principle LLPO, which is not constructive. Similarly it is impossible to find a base $n$ expansion of all computable reals in a uniformly computable way. We'll use this basic idea in the proof below.
There is one curious difference. For general computable functions, we can't find a expansion uniformly, but each computable real individually does have a computable expansion, because both rational and computable irriational numbers have computable expansions. For p.r. reals we can do something much better, which is to find one particular p.r. real with no p.r. expansion.
We basically do this by a diagonal argument. Assume that we are given a primitive recursive surjective pairing operation on $\mathbb{N}$, denoted $(,)$. Also say that we are given a p.r. enumeration of codes for all p.r. functions, represented as codes for Turing machines. We will define a p.r. real $s = (s_i)_{i \in \mathbb{N}}$ in a sequence of "blocks" where in the $n$th block we will ensure that if $n$ codes the pair $(e, r)$ then the $e$th p.r. function is not a p.r. expansion of $s$ in the scale $r$. Along the way we will ensure that for $j, k > i$, $|s_j - s_k| < \frac{1}{10^i}$. Together with defining $s_i$ in a p.r. manner, this will ensure that $s$ is in fact a p.r. real.
Within each block $(e, r)$, we define $s_i$ as follows. Let $i_0$ be the first $i \in \mathbb{N}$ that lies in the block $(e, r)$. Define $q \in \mathbb{Q}$ to be $s_{i_0 - 1}$ if $i_0 > 0$ and $1$ otherwise. Now let $N$ be such that $r^{N} > 2 \times 10^{i_0}$. We can then find in a p.r. way, $k \in \mathbb{N}$ so that $|\frac{k}{r^N} - q| < \frac{1}{2\times 10^{i_0}}$. Let $s_{i_0} := \frac{k}{r^N}$. Now suppose that $(a_j)_{j \in \mathbb{N}}$ is some sequence such that $0 \leq a_j < r$ for all $j$. Then we have that for some $k'$, $\sum_{j = 0}^{N} a_j r^{-j} = \frac{k'}{r^N}$. Note that if $k' < k$, then $\sum_{j = 0}^\infty a_j r^{-j} \leq \frac{k}{r^N}$ and if $k' \geq k$ then $\sum_{j = 0}^\infty a_j r^{-j} \geq \frac{k}{r^N}$. We now ensure that the $e$th p.r. function is not an expansion of $s$ in scale $r$. We can't evaluate $\{e\}(j)$ for $j\leq N$ in a p.r. way, but what we can do is ask whether $\{e\}(j)$ has halted in less than $i$ steps for $j \leq N$. If $\{e\}(j)$ has not yet halted at stage $i$ for some $j \leq N$, we set $s_i := s_{i_0}$. If $\{e\}(j)$ has halted at stage $i$ for every $j \leq N$, we calculate $k'$ as above. If $k' < k$, we define $s_i := s_{i_0} + \frac{1}{3 \times 10^i}$ and from now on ensure that for future $i' > i$, we have $s_{i'} > s_{i_0} + \frac{1}{4 \times 10^i}$. This makes sure that $s > s_{i_0}$. If $k' \geq k$, then we similarly define $s_i := s_{i_0} - \frac{1}{3 \times 10^i}$ and ensure that for $i' > i$, we have $s_{i'} < s_{i_0} - \frac{1}{4 \times 10^i}$, to get $s < s_{i_0}$. However, by the above reasoning this has made sure that $e$ is not a p.r. expansion of $s$ of scale $r$ as required. Finally, note that

Since $e$ is primitive recursive, we know that eventually $\{e\}(j)$ will halt for every $j \leq N$, so we will at some point be able to diagonalise and move on to the next block. This is the crucial difference to general recursive functions.
We can't find the length of each block in a primitive recursive way, but also we don't need to for the argument to work.
{"set_name": "stack_exchange", "score": 5, "question_id": 231461}