A New Kind of Science: The NKS Forum : Powered by vBulletin version 2.3.0 A New Kind of Science: The NKS Forum > Pure NKS > Class 4: important science.
  Last Thread   Next Thread
Thread Post New Thread    Post A Reply
Gledson Melotti


Registered: Oct 2008
Posts: 4

Class 4: important science.

How important is class 4 of a cellular automaton of one dimension in science?

Gledson Melotti

Report this post to a moderator | IP: Logged

Old Post 11-04-2008 10:31 PM
Gledson Melotti is offline Click Here to See the Profile for Gledson Melotti Edit/Delete Message Reply w/Quote
Jason Cawley
Wolfram Science Group
Phoenix, AZ USA

Registered: Aug 2003
Posts: 712

The simplest known universal computational system lies in this class. Well, strictly speaking there are many possible ways of measuring how simple a system is, and 1D CAs with only 2 colors might be the simplest, and are certainly very simple in their allowed number of states and the simplicity of their rules of operation. No one picked this set to have any particular computational property. But it turns out that at least one class 4 rule within this space (and a couple equivalent to it) is provably universal, meaning that it could in principle be programmed to perform any finite computation.

Is this is any great direct, technological or modeling relevance? No. It matters as a lower bound on the internal complexity of a system capable of universal computation. We might have thought that only specially designed computer languages or highly engineered systems would be capable of universal computation, that in a sense we'd have to deliberately put it in, to get it out of any system. But we know from the NKS book and work done for it that this isn't the case. Instead we find that the threshold of universality is quite low, low enough that we can imagine natural systems reaching and exceeding this threshold, without anyone designing them to be computers.

That in turn has implications for how predictable many natural systems may turn out to be. Because once a system is complex enough to support universal computation, we know from theorems of computer science that its future behavior can depend on the exact details of how it starts off, in as sensitive and flexible a manner as our practical computers depend on the details of their programs. Can you predict everything that might ever appear on a laptop screen, without knowing what program it is running?

We say, some natural systems might wind up being computationally irreducible - meaning there could be no way to see exactly what they will do in detail that is any faster than stepping through each stage of their evolution, "one to one". Or watching what the real system does, empirically. There won't be any simple formula that successfully compresses the computational work involved in their behavior (at least, one that gets all the details).

Of course, which natural systems may fall into this category is an empirical question. Nothing about 1D CAs in themselves tell us. But we become aware of the possibility and how easy it may be to reach it, by studying those, and similar simple formal systems.

I hope this helps.

Report this post to a moderator | IP: Logged

Old Post 11-05-2008 07:05 PM
Jason Cawley is offline Click Here to See the Profile for Jason Cawley Click here to Send Jason Cawley a Private Message 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