# 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

 $f(n)=\left\{\begin{array}[]{ll}[r]\textrm{ }(\textrm{the integer part of }r),&% \textrm{if }n=0,\\ n^{\textrm{th}}\textrm{ digit of }r\textrm{ when }r\textrm{ is expressed in % its decimal representation,}&\textrm{if }n\neq 0.\end{array}\right.$

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}\cdots a_{k}},$

we can define $f$ so that

 $f(n)=\left\{\begin{array}[]{ll}[r],&\textrm{if }n=0,\\ a_{i}&\textrm{if }n\neq 0\mbox{ and }n\equiv i\pmod{k}.\end{array}\right.$

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}\cdots n_{k}\cdots$

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

 $10r=n_{0}n_{1}.n_{2}\cdots n_{k}\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}+\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.

## References

Title primitive recursive number PrimitiveRecursiveNumber 2013-03-22 19:06:06 2013-03-22 19:06:06 CWoo (3771) CWoo (3771) 13 CWoo (3771) Definition msc 03D25 msc 68Q05 BombellisMethodOfComputingSquareRoots