Primitive recursive functions and enumerable sets

Posted on by John

The set of primitive recursive (PR) functions is the smallest set of functions of several integer arguments satisfying five axioms:

  1. Constant functions are PR.
  2. The function that picks the ith element of a list of n arguments is PR.
  3. The successor function S(n) = n+1 is PR.
  4. PR functions are closed under composition.
  5. PR functions are closed under primitive recursion.

The last axiom obviously gives PR functions their name. So what is primitive recursion? Given a PR function f  that takes k arguments, and another PR function g that takes k+2 arguments, the primitive recursion of f and g is a function h of k+1 arguments satisfying two properties:

  1. h(0, x1, …, xk) = f(x1, …, xk)
  2. h(S(y), x1, …, xk) = g(y, h(y, x1, … xk), x1, …, xk)

Not every computable function is primitive recursive. For example, Ackermann’s function is a general recursive function, but not a primitive recursive function. General recursive functions are Turing complete. Turing machines, lambda calculus, and general recursive functions are all equivalent models of computation, but the first two are better known.

For this post, the main thing about general recursive functions is that, as the name implies, they are more general than primitive recursive functions.

Now we switch from functions to sets. The characteristic function of a set A is the function that is 1 for elements of A and zero everywhere else. In other areas of math, there is a sort of duality between functions and sets via characteristic functions. For example, the indicator function of a measurable set is a measurable function. And the indicator function of a convex set is a convex function. But in recursive functions, there’s an unexpected wrinkle in this analogy.

A set of integers is recursively enumerable if it is either empty or the image of a general recursive function. But there’s a theorem, due to Alonzo Church, that a non-empty recursively enumerable set is actually the image of a primitive recursive function. So although general recursive functions are more general, you can’t tell that from looking at function images. For example, although the Ackermann function is not primitive recursive, there is a primitive recursive function with the same image.

5 thoughts on “Primitive recursive functions and enumerable sets”

  1. TRVolk

    This takes me back to my junior year at GA Tech. AI changed my world view.

    I am about to do a study of card shuffles (I’m a magician) so I can manage upcoming permutations in my head during performance. You just furnished my first page of notes. Thanks!

    I will let you know if I uncover anything tasty.

  2. Pieter van Engelen

    You have a pointer to the article/book where Church proves this wrinkly theorem? I’m having trouble finding it due to the changing nomenclature for general recursive, primitive recursive, \mu-recursive etc.
    I would be much obliged.

  3. Pieter van Engelen

    I took out Odifreddi’s Classical Recursion Theory.

    The theorem you stated might actually be true, but I couldn’t find it to be due to Church. Kleene is our man in this respect. In his 1936 article ‘General recursive functions of natural numbers’ he proves two important theorems:
    (1) Set A is r.e. iff A is empty or A is the range of a recursive function
    (2) Normal Form Theorem: there’s a primitive recursive evaluation function, which evaluates general recursive functions, using only one unbounded minimalisation. The proof of this thm hinges on the use of a Gödel codingfunction voor primrec functions.

    This is the closest I could find to your statement. There’s still one unbounded scoundrel in the way though…

    Continuing the search…

Comments are closed.