# [WSC17] Enumerating and Visualizing Primitive Recursive Functions

Posted 1 year ago
1028 Views
|
0 Replies
|
1 Total Likes
|
 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: https://www.wolframscience.com/nks/notes-4-3--primitive-recursive-functions/ WolframMathWorld page on Ackermann Function: http://mathworld.wolfram.com/AckermannFunction.htmlAn example of a very basic function with simple behavior is r[z, r[s,s]][x, y]:Explicit formula: f[x_,y_]=x*(x+1)/2+y+1An example with more irregular behavior is r[z, r[s, r[p(1), p(1)]]][x] :Explicit formula: f[x_]:=Power[2, 1 + Floor[Log[2, x]]] - x-1 for x≥1, f[0]=1In 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]: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.