examples of primitive recursive encoding

In this entry, we present three examples of primitive recursive encodings. In all the examples, the following notations are used: is the set of all natural numbersMathworldPlanetmath (including 0), * is the set of all finite sequencesPlanetmathPlanetmath over , and E:* is the encoding in question. For any sequence a1,,ak, its image under E is denoted by a1,,ak, and is called the sequence number corresponding to a1,,ak. Furthermore, () denotes the empty sequence, and its sequence number is denoted by . The fact that the E in each of the examples below is in fact encoding is proved in this entry (http://planetmath.org/EncodingWords).

Example 1. (Multiplicative encoding) E is defined as follows:

:= 1,
a1,,ak := p1s(a1)pks(ak),

where s is the successor function, and p1,,pk are the first k prime numbersMathworldPlanetmath.

To see that E is primitive recursive, we verify the following:

  • the predicateMathworldPlanetmathx is a sequence number” is primitive recursive: a number x is a sequence number iff x=1 or, if p|x for some prime p, then q|x for any prime qp. The predicates

    Φ1:=``p|x for some prime p``px(P(p)(p|x)),
    Φ2:=``p is prime and q|x for all primes qp``qp(P(p)P(q)(q|x))

    where P(r):=r is prime”, are primitive recursive by bounded quantification. Thus “x is a sequence number” iff “x=1 or Φ1Φ2” iff “(x=1)(¬Φ1Φ2)”, is primitive recursive as a result.

  • Ek(a1,,ak):=p1s(a1)pks(ak) is clearly primitive recursive.

  • lh(x) can be defined as the number of primes dividing x, which is primitive recursive.

  • (x)y can be defined as the exponent of the y-th prime in x (the largest power of py dividing x), which is again primitive recursive.

Example 2. (Encoding via a pairing functionMathworldPlanetmath) First, let J:2 be a (primitive recursive) pairing function. For any n2, define

J2(x1,x2) := J(x1,x2)
Jn+1(x1,,xn,xn+1) := J(x1,Jn(x2,,xn+1)).

Then define E by

:= 0,
a1,,ak := J(k,Jk(a1,,ak)).

E is primitive recursive because

  • E is a bijection, so the predicate “x is a sequence number” is the same as “x”, which is clearly primitive recursive,

  • Ek(a1,,ak):=J(k,Jk(a1,,ak)) is primitive recursive since both J and Jk are, the latter of which can be shown to be primitive recursive by inductionMathworldPlanetmath,

  • The two functions R,L: such that J(L(m),R(m))=m are primitive recursive. So lh(x)=L(x) in particular is primitive recursive.

  • If Jk(a1,,ak)=b, then a1=L(b),a2=LRL(b),,ak-1=(LR)k-2L(b), and ak=R(LR)k-2L(b). Thus,

    (x)y={(LR)y(x)if y<L(x),R(LR)y(x)if y=L(x),0otherwise.

    is primitive recursive, since each case is primitive recursive.

Example 3. (Digital Representation) Pick a positive integers p>1. Define E by

:= 1
a := ps(a)
a1,,ak,ak+1 := a1(a2,,ak+1+1).

In other words,

a1,,ak=ps(a1)+ps(a1)+s(a2)+ps(a1)++s(ak). (1)

To see that E is primitive recursive, we first define three functions f: given by f(x):=lo(p,x), the exponent of p in x, g: given by g(x):=quo(x,pf(x))-˙1, and h:2 given by

h(x,0) := x
h(x,n+1) := g(h(x,n)).

Clearly, f,g,h are all primitive recursive. Furthermore, h has the property that if h(x,n)>0, then h(x,n+1)<h(x,n), and therefore h(x,n)=0 for large enough n. Using h, we may proceed to show that E is primitive recursive:

  • the predicate “x is a sequence number” is equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath to the predicate


    which is equivalent to the predicate


    since p>1. As the quantification is bounded, the predicate is primitive recursive.

  • Ek(a1,,ak)=a1,,ak is primitive recursive by equation (1) above.

  • lh(x) can be defined as the number of n such that h(x,n)0, or


    which is primitive recursive, because it is a bounded sum.

  • If a1,,ak=x, then f(h(x,0))=s(a1),,f(h(x,k-1))=s(ak). Therefore, (x)y is just f(h(x,y-˙1))-˙1, which is primitive recursive.

Remark. In the third example, E can be more generally defined so that


provided that p,q are coprimeMathworldPlanetmath. It is fairly straightforward to show that E is again primitive recursive.

Title examples of primitive recursive encoding
Canonical name ExamplesOfPrimitiveRecursiveEncoding
Date of creation 2013-03-22 19:06:23
Last modified on 2013-03-22 19:06:23
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 8
Author CWoo (3771)
Entry type Example
Classification msc 94A60
Classification msc 68Q45
Classification msc 68Q05
Classification msc 03D20