primitive recursive number

A special of computable numbersMathworldPlanetmath is so-called the primitive recursive numbers. Informally, these are numbers that can be measured by primitive recursive functionsMathworldPlanetmath 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: such that

f(n)={[r] (the integer part of r),if n=0,nth digit of r when r is expressed in its decimal representation,if n0.

A real number r is primitive recursive if |r| is, and a complex numberMathworldPlanetmathPlanetmath 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


we can define f so that

f(n)={[r],if n=0,aiif n0 and ni(modk).

Here, we assume that r is non-negative.

In additionPlanetmathPlanetmath, we can show that n is primitive recursive for any non-negative integer n.


Suppose r=n. Write r in its decimal representation


Then n0=[n]. Multiply r by 10 to get its decimal representation


Then 10n0+n1=[10r]=[100n], so that n1=[100n]-10n0 By inductionMathworldPlanetmath, we see that


Define f:2 by f(n,m)=nm. Then f(n,0) is primitive recursive. Next,




which is primitive recursive (all of the operationsMathworldPlanetmath, 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 π is primitive recursive. A proof of this can be found in the link below.


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