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
|
11-04-2008 10:31 PM
