# 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)=\{\begin{array}{cc}[r]\text{}(\text{the integer part of}r),\hfill & \text{if}n=0,\hfill \\ {n}^{\text{th}}\text{digit of}r\text{when}r\text{is expressed in its decimal representation,}\hfill & \text{if}n\ne 0.\hfill \end{array}$$ |

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

$$f(n)=\{\begin{array}{cc}[r],\hfill & \text{if}n=0,\hfill \\ {a}_{i}\hfill & \text{if}n\ne 0\text{and}n\equiv i\phantom{\rule{veryverythickmathspace}{0ex}}(modk).\hfill \end{array}$$ |

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 $10{n}_{0}+{n}_{1}=[10r]=[\sqrt{100n}]$, so that ${n}_{1}=[\sqrt{100n}]-10{n}_{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.

## References

- 1 S. G. Simpson, http://www.math.psu.edu/simpson/courses/math558/fom.pdfFoundations of Mathematics. (2009).

Title | primitive recursive number |
---|---|

Canonical name | PrimitiveRecursiveNumber |

Date of creation | 2013-03-22 19:06:06 |

Last modified on | 2013-03-22 19:06:06 |

Owner | CWoo (3771) |

Last modified by | CWoo (3771) |

Numerical id | 13 |

Author | CWoo (3771) |

Entry type | Definition |

Classification | msc 03D25 |

Classification | msc 68Q05 |

Related topic | BombellisMethodOfComputingSquareRoots |