## You are here

Homeprimitive recursive number

## Primary tabs

# primitive recursive number

A special type 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\;\;(\mathop{{\rm mod}}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

- 1 S. G. Simpson, Foundations of Mathematics. (2009).

## Mathematics Subject Classification

03D25*no label found*68Q05

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections