primitive recursive encoding

Recall that an encoding of a set L of words over some alphabetMathworldPlanetmath Σ is defined as an injective function E:L, the set of natural numbers (including 0 here).

Finite sequencesPlanetmathPlanetmath over can be thought of as words over the “infiniteMathworldPlanetmath” alphabet . So the notion of word encoding directly carries over to encoding of finite sequences of natural numbersMathworldPlanetmath. Let * be the set of all finite sequences over .

Definition. Let E be an encoding for *. A number is called a sequence number if it is in the range of E. Since E is injective, we say that E(a) is the sequence number of the sequence a.

Once E is fixed, we also use the notation a1,,ak to mean the sequence number of the sequence a1,,ak.

Define the following operationsMathworldPlanetmath on associated with a given E:

  1. 1.

    En:=E|n*, the restrictionPlanetmathPlanetmathPlanetmath of E to the set n* of all sequences of length n, and E0 is defined as the number .

  2. 2.

    the length function: lh::

    lh(x):={z,if E-1(x) exists, and has length z,0,otherwise.
  3. 3.

    ():2, such that

    (x)y:={z,if E-1(x) exists, has length y, with z its y-th number,0,otherwise.
  4. 4.

    *:2, such that

    x*y:={E(ab),where E(a)=x and E(b)=y,0,otherwise.

    The notation ab stands for the concatenationMathworldPlanetmath of the sequences a and b.

  5. 5.

    ext:2, such that

    ext(x,y):={E(ay),where E(a)=x,0,otherwise.

    The notation ay stands for the sequence a, extended by appending y to the right of a.

  6. 6.

    red:, such that

    red(x):={z,where E(a)=x and E(b)=z such that a=bc and c,0,otherwise.

    In other words, z is the sequence number of the sequence obtained by removing the last (rightmost) number (if any) in the sequence whose sequence number is x, provided that x is a sequence number.

Definition. An encoding E for * is said to be primitive recursive if

  • E(*) is a primitive recursive set, and

  • the first three types of functions defined above are primitive recursive.

Proposition 1.

If E is primitive recursive, so are the functions *,ext, and red.


Let χ(x) be the characteristic functionMathworldPlanetmathPlanetmathPlanetmath of the predicatex is a sequence number” (via E). It is primitive recursive by assumptionPlanetmathPlanetmath.

  1. 1.

    Let n=lh(x)+lh(y). Then x*y=En((x)1,,(x)lh(x),(y)1,,(y)lh(y))χ(x)χ(y), which is primitive recursive.

  2. 2.

    Let n=lh(x)+1. Then ext(x,y)=En((x)1,,(x)lh(x),y)χ(x), which is primitive recursive.

  3. 3.

    Let n=lh(x)-˙1. Then

    red(x)={En((x)1,,(x)lh(x)-˙1),if lh(x)>1, and χ(x)=1,if lh(x)=1, and χ(x)=10,otherwise,

    which is primitive recursive.

Examples of primitive recursive encoding can be found in the parent entry (methods 2, 3, and 7).

Title primitive recursive encoding
Canonical name PrimitiveRecursiveEncoding
Date of creation 2013-03-22 19:06:20
Last modified on 2013-03-22 19:06:20
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 7
Author CWoo (3771)
Entry type Definition
Classification msc 68Q05
Classification msc 68Q45
Classification msc 03D20
Classification msc 94A60
Defines sequence number