Course of values : depends on everything computed so far
In[]:=
Clear[s,z,p,c,g,h,r]
In[]:=
z=0&​​s=#+1&​​p[i_]=Slot[i]&​​c[g_,h___]=Apply[g,Through[{h}[##]]]&​​r[g_,h_]=If[#10,g[##2],h[#0[#1-1,##2],#1-1,##2]]&​​
In[]:=
r[g_,h_]:=Fold[Function[{u,v},h[u,v,##2]],g[##2],Range[#1]]&
In[]:=
z=0&;​​s=#+1&;​​p=Function@*Slot;​​c[g_,h___]:=Through[Unevaluated[g[h][##]]]&
In[]:=
plus=r[p[1],s];
In[]:=
mul=r[z,c[plus,p[1],p[3]]];
mul=r[z,c[r[p[1],s],p[1],p[3]]];
In[]:=
mul[3,4]
Out[]=
12
c[s,c[s,z]]
In[]:=
r[c[s,z],c[f,c[s,p[2]]]][-1]
Out[]=
1
In[]:=
f@*g
Out[]=
f@*g
In[]:=
FullForm[%]
Out[]//FullForm=
Composition[f,g]
In[]:=
r[p[1],s][2,3]
Out[]=
5
​
In[]:=
p[1]
Out[]=
#1&
In[]:=
z[x]
Out[]=
0
In[]:=
s[x]
Out[]=
1+x
In[]:=
p[1][x,y]
Out[]=
x
In[]:=
c[f,g][x,y]
Out[]=
f[g[x,y]]
In[]:=
r[f,g][1,1]
Out[]=
g[f[1],0,1]
In[]:=
Table[With[{i=i},HoldForm[r[f,g][i,x]]]->r[f,g][i,x],{i,0,2}]
Out[]=
{r[f,g][0,x]f[x],r[f,g][1,x]g[f[x],0,x],r[f,g][2,x]g[g[f[x],0,x],1,x]}
In[]:=
r[f,g][1,x]
Out[]=
g[f[x],0,x]
In[]:=
r[f,g][2,x]
Out[]=
g[g[f[x],0,x],1,x]
In[]:=
r[p[1],s][2,3]
Out[]=
5
In[]:=
#1&[x,y,z]
Out[]=
x
In[]:=
r[p[1],s][5,6]
Out[]=
5+0[6]
In[]:=
r[p[1],s][5]
Out[]=
5+0[]
In[]:=
Array[r[z,r[s,s]],20]
Out[]=
{1,3,6,10,15,21,28,36,45,55,66,78,91,105,120,136,153,171,190,210}
In[]:=
Array[r[z,r[s,r[s,s]]],4]
Out[]=
{1,3,9,49}
Fold[{a,b}|->1/2a(a+1)+b,0,Range[#]]
Need to encode sequences of numbers so far.... as a single number
Primitive recursion: Computed just using Fortran Do[ ] loops
f[n_]" := "n-
f
f[n-1]

If only uses Nest, not NestWhile ....
Hierarchy is how many nested Nest[ ], Fold[ ] (or nested Do[ ])
Ackermann
In[]:=
First/@NestList[Rest[Append[#,Total[#]]]&,{1,1},10]
Out[]=
{1,1,2,3,5,8,13,21,34,55,89}
In[]:=
FoldList[Append[#,#2-#[[Last[#]]]]&,{1},Range[10]]
Part
:The expression 2-List cannot be used as a part specification.
Part
:The expression 3-{1,0,2-List}〚2-List〛 cannot be used as a part specification.
Part
:The expression 4-{1,0,2-List,3-{3}〚Plus[2]〛}〚3-{1,0,Plus[2]}〚2+Times[2]〛〛 cannot be used as a part specification.
General
:Further output of Part::pkspec1 will be suppressed during this calculation.
Out[]=
{1},
⋯9⋯
,1,
⋯9⋯
,10-1,
⋯8⋯
,9-1,0,
⋯5⋯
,7-
⋯1⋯
,8-1,
⋯6⋯
,7-1,
⋯5⋯
,6-1,0,
⋯2⋯
,4-
⋯1⋯
,5-1,
⋯3⋯
,4-{1,0,
⋯1⋯
,3-
⋯1⋯
}3-
⋯1⋯
4-
⋯1⋯

⋯1⋯
6-
⋯1⋯
7-
⋯1⋯
8-
⋯1⋯
9-
⋯1⋯

Full expression not available
(
original memory size:
1.4 MB)
​
In[]:=
Fold[Append[#1,#2-#1[[#1[[#2]]+1]]]&,{0},Range@76]
Out[]=
{0,1,1,2,3,3,4,4,5,6,6,7,8,8,9,9,10,11,11,12,12,13,14,14,15,16,16,17,17,18,19,19,20,21,21,22,22,23,24,24,25,25,26,27,27,28,29,29,30,30,31,32,32,33,33,34,35,35,36,37,37,38,38,39,40,40,41,42,42,43,43,44,45,45,46,46,47}
WHat level of G hierarchy? (G hierarchy assumes only successor)
n steps of TM: if PR
What does it eventually output?
For what n is f[n] > 1000? Not obviously PR ....
f[n]>1000
Out[]=
Out[]=
f[n_] := 2
fn-
f[n-2]

In[]:=
Ramp[-5]
Out[]=
0
r works as a conditional......
Fold[Append[#1,2#1[[If[#<=0,1,#]&[#2-#1[[#2-2]]]]]]&,{0},Range@10]
Part
:Part 2 of {0} does not exist.
Part
:The expression 1+If[2-List≤0,1,2-List] cannot be used as a part specification.
Part
:Part 4 of {0,2{0}〚2〛,2{0,2{0}〚2〛}〚1+If[2+Times[2]≤0,1,2-List]〛} does not exist.
Part
:The expression 1+If[4-2{0}〚2〛≤0,1,4-2{0}〚2〛] cannot be used as a part specification.

Ackermann

https://www.wolframscience.com/nks/notes-4-3--ackermann-functions/

Pairing

Ackermann

Termination

Fibonacci PR

Call Trees