Message Boards Message Boards

[WSC17] Enumerating and Visualizing Primitive Recursive Functions


Hi! I am Jeffrey Shi and my project this year for the Wolfram High School Summer Program was to study Primitive Recursive Functions and their behavior. I chose this particular project because I have always been interested in data collection and data analysis. Primitive Recursive Functions are a special class of functions that are composed of 3 basic functions: the Successor function, the Projection function, and the Zero function. These three functions are then combined using two functions: the Composition function and the Primitive Recursion function. With these 5 functions, a vast array of functions that produce a diverse range of data can be created. What is particularly interesting about these functions is that almost all mathematical functions can be expressed as a primitive recursive sequence. One of the very few exceptions is the Ackermann function.

NKS page on Primitive Recursive Functions: WolframMathWorld page on Ackermann Function:

An example of a very basic function with simple behavior is r[z, r[s,s]][x, y]:

enter image description here

Explicit formula: f[x_,y_]=x*(x+1)/2+y+1

An example with more irregular behavior is r[z, r[s, r[p(1), p(1)]]][x] :

enter image description here

Explicit formula: f[x_]:=Power[2, 1 + Floor[Log[2, x]]] - x-1 for x≥1, f[0]=1

In the two examples above both had a closed explicit form of expressing the function. However, there are certain ones where there are no closed explicit form (or there is not an immediately apparent closed form).

One such example is r[s, r[z, r[p(1), s]]][x,y]:

enter image description here

This example is based off a Binomial "nesting" pattern. When x=1, the function represents Binomial[y,2], when x=2, it represents Binomial[Binomial[y,2],2]. This pattern continues with an additional "layer" added each time to the expression. It is still unknown if a closed form of this function exists.

Below is a snapshot of a portion of the data table that I compiled as I tested various primitive recursive functions.

enter image description here

POSTED BY: Jeffrey Shi
18 days ago

Group Abstract Group Abstract