# 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. – Simon Woods Jan 28 '16 at 21:21
• @SimonWoods That one was specifically for the primitive recursion operator. – user76284 Jan 28 '16 at 21:23
• When early H. Sapiens painted pictures of themselves painting on cave walls, was that primitive recursion? – Daniel Lichtblau Jan 28 '16 at 21:30
• Related: (1532) – Oleksandr R. Jan 28 '16 at 22:15
• Steven W. takes crack at defining primitive recursive functions in M here:wolframscience.com/nks/notes-4-3--primitive-recursive-functions – Christopher Lamb Feb 28 '18 at 20:11

## 1 Answer

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
(* 0 *)

• Successor function

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

• Projection function

proj[n_Integer] = {##}[[n]] &;
proj[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[x]
add[n_, x_] := succ[proj[n - 1, add[n - 1, x], x]]


but it cannot be implemented via

add[0, x_] := proj[x]
add[succ[n_], x_] := succ[proj[n, add[n, x], x]]


which is the official definition of the primitive recursive binary sum function in terms of the basic primitive recursive functions.

• How would you express the add function directly in terms of prec? – user76284 Feb 1 '16 at 17:19
• @user1667423. I don't know. Do you know how it's done "formally"? That is, if you have a link to something that shows how to do it symbolically (similar to what's done on the Wikipedia page on primitive recursion, which is basically what I used to learn about this), then I can probably interpret it in terms of the Mathematica language. Otherwise, you should probably do some of this work yourself. – march Feb 1 '16 at 17:24
• Ah, I found the answer under en.wikipedia.org/wiki/Primitive_recursive_function#Addition. So f is proj and g is comp[succ, proj] in add = prec[f, g]. Thanks for your help with this question! – user76284 Feb 12 '16 at 2:28