Deeper Nesting
Deeper Nesting
In[]:=
ListLinePlot[RecursiveFunction[f[n]->n-f[n-f[n-1]],{}->{},{n<=1->1}][Range[200]]]
Out[]=
In[]:=
ListLinePlot[RecursiveFunction[f[n]->n-f[n-f[f[n-1]]],{}->{},{n<=1->1}][Range[200]]]
Out[]=
In[]:=
ListLinePlot[RecursiveFunction[f[n]->n-f[n-f[f[f[n-1]]]],{}->{},{n<=1->1}][Range[200]]]
Out[]=
In[]:=
ListLinePlot[RecursiveFunction[f[n]->n-f[n-f[f[f[f[n-1]]]]],{}->{},{n<=1->1}][Range[200]]]
Out[]=
In[]:=
ListLinePlot[RecursiveFunction[f[n]->n-f[n-f[f[n-1]]],{}->{},{n<=1->1}][Range[1000]]-Range[1000]/N[GoldenRatio]]
Out[]=
TableListLinePlotRecursiveFunction[f[n]->n-f[n-f[f[f[n-a]]]],{}->{},{n<=1->1}][Range[1000]]-Range[1000]N,{a,10}
In[]:=
x==1-x(1-x^d)//Simplify
Out[]=
1+2x
1+d
x
In[]:=
Solve[x^4-2x+1==0,x]
Out[]=
{x1},x,x,x
In[]:=
RootReduce
In[]:=
N
Out[]=
0.543689
In[]:=
-1+#1++&[x]
2
#1
3
#1
Out[]=
-1+x++
2
x
3
x
[]
3
x
2
x
In[]:=
Table[Min[Select[NSolveValues[-2x+1==0,x,Reals],Positive]],{d,5}]
d+1
x
Out[]=
{1.,0.618034,0.543689,0.51879,0.50866}
In[]:=
Nest[f,x,2]
Out[]=
f[f[x]]
In[]:=
With{len=500,a=1},ResourceFunction["PlotGrid"]PartitionFunction{d},ListStepPlotRecursiveFunction[f[n]->n-f[n-Nest[f,n-a,d]],{}->{},{n<=1->1}][Range[len]]-Range[len]Min[Select[NSolveValues[-2x+1==0,x,Reals],Positive]],Center,AspectRatio->14,Frame->True,FrameTicks->None,PlotRangePadding->2,Epilog->Text[Row[{Subscript["N",d],a}],Scaled[{.1,.8}]]/@Range[2,7],2
d+1
x
Out[]=
In[]:=
With{len=5000,a=1},ResourceFunction["PlotGrid"]PartitionFunction{d},ListStepPlotRecursiveFunction[f[n]->n-f[n-Nest[f,n-a,d]],{}->{},{n<=1->1}][Range[len]]-Range[len]Min[Select[NSolveValues[-2x+1==0,x,Reals],Positive]],Center,AspectRatio->14,Frame->True,FrameTicks->None,PlotRangePadding->2,Epilog->Text[Row[{Subscript["N",d],a}],Scaled[{.1,.8}]]/@Range[2,7],2
d+1
x
Out[]=
In[]:=
With{len=500,a=2},ResourceFunction["PlotGrid"]PartitionFunction{d},ListStepPlotRecursiveFunction[f[n]->n-f[n-Nest[f,n-a,d]],{}->{},{n<=1->1}][Range[len]]-Range[len]Min[Select[NSolveValues[-2x+1==0,x,Reals],Positive]],Center,AspectRatio->14,Frame->True,FrameTicks->None,PlotRangePadding->2,Epilog->Text[Row[{Subscript["N",d],a}],Scaled[{.1,.8}]]/@Range[2,7],2
d+1
x
Out[]=
More Terms
More Terms
Nested Inside
Nested Inside
S family
S family
Rendering each value as a separate dot, this becomes:
Evaluation Graphs
Evaluation Graphs
Computational Complexity
Computational Complexity
Could it have bounded behavior for increasing n [ could it bound itself ]
Should also sow for f[1] etc.
For Plus rules,
Using red first, then backtracking to blue....
[[ This contains some double edges ]]]
Equal to sum of path counts .....
Each function has two function calls....
Size of unrolled graph vs. size of call graph?
Longest path is red path... Which is of length n, n/2 , etc. Maximum tree size is 2^XXXX
Primitive Recursive Function
Primitive Recursive Function
[[ If function is below f[n] ≤ n then there must be bounded lookback; for S family ]]
Lookback is bounded by a primitive recursive function of n ....
Is <= 0 PR?
How do you deal with the function being negative?
Universal Function
Universal Function
Normally e.g. a CA is PR....
Does there exist a value of n for which f[n] is ____ : not PR
Does there exist a value of n for which f[n] is ____ : not PR
Can make a converter from NRF to PR ....
Can make a converter from NRF to PR ....
Successor....
Given n , you know how many steps to compute g[n] .... Problem with Ackermann is that even to compute that function is
w is set of all PR functions w[[m]]
Then we make a function from this that does not appear in the list w
Ackermann is a double recursion.....