characterization of primitive recursive functions of one variable

It is possible to characterize primitive recursive functionsMathworldPlanetmath of one variable in terms of operationsMathworldPlanetmath involving only functionsMathworldPlanetmath of a single variable. To describe how this goes, it is useful to first define some notation.

Definition 1.

Define the constant functionMathworldPlanetmath K:NN by K(n)=1 for all n.

Definition 2.

Define the identity functionMathworldPlanetmath I:NN by I(n)=n for all n.

Definition 3.

Define the excess over square function E:NN by E(n)=n-m2, where m is the largest integer such that m2n.

Definition 4.

Given a function f:NN, define the function R(f):NN by the following conditions:

  • R(f)(0)=0

  • R(f)(n+1)=f(R(f)(n)) for all integers n0.

Theorem 1.

The class of primitive recursive functions of a single variable is the smallest class X of functions which contains the functions E and K defined above and is closed under the following three operations:

  1. 1.

    If fX and gX, then fgX.

  2. 2.

    If fX, then f+IX. 11Here f+I has the usual meaning of pointwise addition(f+I)(x)=f(x)+I(x)

  3. 3.

    If fX, then R(f)X.

Title characterization of primitive recursive functions of one variable
Canonical name CharacterizationOfPrimitiveRecursiveFunctionsOfOneVariable
Date of creation 2013-03-22 16:45:25
Last modified on 2013-03-22 16:45:25
Owner rspuzio (6075)
Last modified by rspuzio (6075)
Numerical id 9
Author rspuzio (6075)
Entry type Theorem
Classification msc 03D20