[recursion's complexity class] - A New Kind of Science: The NKS ForumA New Kind of Science: The NKS Forum
Pages:1
recursion's complexity class
(Click here to view the original thread with full colors/images)
Posted by: Philip Ronald Dutton
In terms of NKS complexity classes (I-IV), 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.
Forum Sponsored by Wolfram Research
© 2004-2008 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. |
Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings