The basic primitive recursive functions

How can the basic primitive recursive functions be expressed in the Wolfram Language?

Apparently here's an example for primitive recursion:

prRec[f_, g_] :=If[#1 === 0, f[##2], g[#1 - 1, #0[#1 - 1, ##2], ##2]] &


The basic primitive recursive functions are:

• Zero function $0$
• Successor function $S(k) = k + 1$
• Projection function $\pi_i(x_1,\ldots,x_i,\ldots)=x_i$
• Composition
• Primitive recursion
• Could you expand the question a bit? Specifically, state how the included example fails to answer the question, and how the question is different from the one you linked. Jan 28, 2016 at 21:21
• @SimonWoods That one was specifically for the primitive recursion operator. Jan 28, 2016 at 21:23
• When early H. Sapiens painted pictures of themselves painting on cave walls, was that primitive recursion? Jan 28, 2016 at 21:30
• Related: (1532) Jan 28, 2016 at 22:15
• Steven W. takes crack at defining primitive recursive functions in M here:wolframscience.com/nks/notes-4-3--primitive-recursive-functions Feb 28, 2018 at 20:11

Some of these could be implemented differently, of course, but I've gone the way of making all of them pure functions (in the Mathematica sense). Every single one takes a Sequence of arguments as the inputs, but some of them accept function names as inputs first, and the projection function accepts an integer for which argument is chosen (I have chosen to use Mathematica indexing which starts at one).

• Zero function

zero = 0 &;
zero[5]
(* 0 *)

• Successor function

succ = # + 1 &;
succ /@ Range[10]
(* {2, 3, 4, 5, 6, 7, 8, 9, 10, 11} *)

• Projection function

proj[n_Integer] = {##}[[n]] &;
proj[3][a, b, c, d]
(* c *)


or

proj[n_Integer] := Slot[n] &

• Composition

comp[f_, gs__] = f @@ Through@{gs}@## &;
comp[f, g1, g2, g3][a, b, c, d, e]
(* f[g1[a, b, c, d, e], g2[a, b, c, d, e], g3[a, b, c, d, e]] *)

• Primitive Recursion: with this one, you need to be careful. It assumes that the first argument is a non-negative integer. If it is not, there will be an infinite recursion.

prec[f_, g_] = If[#1 == 0, f[##2], g[#1 - 1, #0[#1 - 1, ##2], ##2]] &;
prec[f, g][3, x, y, z]
(* g[2, g[1, g[0, f[x, y, z], x, y, z], x, y, z], x, y, z] *)


Possible issue, based on my lack of knowledge about how this is implemented. The successor function seems to be what is used to decrement arguments to the function in order to define things recursively. For instance, the binary add function can be implemented via

add[0, x_] := proj[1][x]

add[0, x_] := proj[1][x]

• How would you express the add function directly in terms of prec? Feb 1, 2016 at 17:19
• Ah, I found the answer under en.wikipedia.org/wiki/Primitive_recursive_function#Addition. So f is proj[1] and g is comp[succ, proj[2]] in add = prec[f, g]. Thanks for your help with this question! Feb 12, 2016 at 2:28