Philip Ronald Dutton
independent
Columbia, SC
Registered: Feb 2004
Posts: 172 
recursion's complexity class
In terms of NKS complexity classes (IIV), where is recursion? I am guessing most people will place it with "nesting" which is class II(?).
Does the NKS book talk specifically about recursion in terms of complexity class? In my opinion I feel as if it is almost impossible to make any sense out of recursion (or nesting for that matter) without a reference point.
In particular, I look at the natural numbers this way when viewed in terms of the Peano axioms. It seems that you can not talk about natural numbers at all unless you have somehow defined them in terms of a reference point.
If recursion and nesting are the same thing and if they are completely inseparable from a reference point, then it is easy to see how number systems mirror this. An obvious example is when looking at the binary representation of the number sequence as can be seen in the NKS book or by simple programming.
So, how does the reference point come about? Peano axioms do not seem to clearly define a reference point (note: the axiom "1 is a natural number" doesn't work as fulfilling the role).
My point is that, perhaps, all nesting systems can be understood a little more in terms of this idea that there must be a reference point before there can be nesting or recursion. I have tried to take the Rule 90 ECA and figure out where the reference point is. Perhaps the reference point is the initial condition no matter what the initial condition is.
__________________
P h i l i p . R . D u t t o n
Report this post to a moderator  IP: Logged
