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

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