A New Kind of Science: The NKS Forum : Powered by vBulletin version 2.3.0 A New Kind of Science: The NKS Forum > NKS Way of Thinking > recursion's complexity class
  Last Thread   Next Thread
Thread Post New Thread    Post A Reply
Philip Ronald Dutton
Columbia, SC

Registered: Feb 2004
Posts: 172

recursion's complexity class

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.

P h i l i p . R . D u t t o n

Report this post to a moderator | IP: Logged

Old Post 08-06-2007 08:20 PM
Philip Ronald Dutton is offline Click Here to See the Profile for Philip Ronald Dutton Click here to Send Philip Ronald Dutton a Private Message Visit Philip Ronald Dutton's homepage! Edit/Delete Message Reply w/Quote
Post New Thread    Post A Reply
  Last Thread   Next Thread
Show Printable Version | Email this Page | Subscribe to this Thread


wolframscience.com  |  wolfram atlas  |  NKS online  |  Wolfram|Alpha  |  Wolfram Science Summer School  |  web resources  |  contact us

Forum Sponsored by Wolfram Research

© 2004-16 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer | Archives