primitive recursive number

A special of computable numbers is so-called the primitive recursive numbers. Informally, these are numbers that can be measured by primitive recursive functions to an arbitrary degree of precision.

Definition. A non-negative real number $r$ is said to be primitive recursive if there is a primitive recursive function $f:\mathbb{N}\to \mathbb{N}$ such that

A real number $r$ is primitive recursive if $|r|$ is, and a complex number $x+yi$ is primitive recursive if both $x$ and $y$ are.

Clearly, any integer is primitive recursive. It is easy to see that all rational numbers are primitive recursive too, as the decimal representation of a rational number is periodic, so if

$$r=[r].\overline{a_1\mathrm{\cdots }{a}_k},$$

we can define $f$ so that

Here, we assume that $r$ is non-negative.

In addition, we can show that $\sqrt{n}$ is primitive recursive for any non-negative integer $n$.

Proof.

Suppose $r=\sqrt{n}$. Write $r$ in its decimal representation

$$r=n_0.n_1{n}_2\mathrm{\cdots }{n}_k\mathrm{\cdots }$$

Then $n_0=[\sqrt{n}]$. Multiply $r$ by $10$ to get its decimal representation

$$10r=n_0{n}_1.n_2\mathrm{\cdots }{n}_k\mathrm{\cdots }$$

Then $10n_0+n_1=[10r]=[\sqrt{100n}]$, so that $n_1=[\sqrt{100n}]-10n_0$ By induction, we see that

$$n_{k+1}=[\sqrt{{100}^{k+1}n}]-10({10}^k{n}_0+{10}^{k-1}{n}_1+\mathrm{\cdots }+n_k).$$

Define $f:{\mathbb{N}}^2\to \mathbb{N}$ by $f(n,m)=n_m$. Then $f(n,0)$ is primitive recursive. Next,

$$f(n,m)=[\sqrt{{100}^{m}n}]-10\sum _{i=0}^{m-1}{10}^{m-1-i}f(n,i)=h(n,m,\overline{f}(n,m)),$$

where

$$h(x,y,z)=[\sqrt{{100}^{x}y}]\dot{-}10\sum _{i=0}^{y\dot{-}1}{10}^{y\dot{-}s(i)}{(z)}_i$$

which is primitive recursive (all of the operations, including the bounded sum are primitive recursive). Since $f$ is defined by course-of-values recursion via $h$, $f$ is primitive recursive also.∎

Remark. It can be shown that $\pi$ is primitive recursive. A proof of this can be found in the link below.