Registered: Mar 2004
Posts: 19

I have been thinking lately about the way that things can go together and the way that things tend to go together. With the 256 simplest CA rules Wolfram has shown (to most people) that they tend towards four seperate classes. And they do not do so equally. It seems that most rule sets, including infinite ones, are the same way.

Why?

The fact that CA's and simple programs in general are capable of universal computation and therefore to mimic any desired degree of complexity is interesting. That nature mirrors herself in her parts through possibly simple means is astounding to most. Most would guess that seeing the complexity of the natural world that the laws of the universe should be hard to understand. While in fact they may be simple to understand (though very hard to find).

The emergence of complexity and the emergence of class four behaviour within a given rule set, to me, is an interesting problem. I'm sure there is, if not an abundance, some data regarding the percentages of class division within different rule sets. Is there an overall trend?

Class 3 behaviour is particularily interesting. If Class 3's are indeed capable of universal computation then nature is capable of organization within her most disorganized parts. What could this imply regarding the construction of things, in general, within the natural world?

Any ideas?

Jason

Report this post to a moderator | IP: Logged

Registered: Aug 2003
Posts: 712

As you add computational resources to a system type - more states, longer ranged interactions, less regular ones, etc - there is a characteristic sequence one sees in the class portions. At first there are only simple behaviors - the system just doesn't have enough going on yet to support complexity. Then a few cases of more intricate but still reducible behavior appear - nested behavior being the characteristic one at this point - as a significant portion, while most are still simple.

Then with another uptick in system resources, one sees class 3s (mixed looking chaos) and more nesting, fair portions of both but still plenty of simplicity. 4 are rare even later on, and it is not clear whether their not showing up right away in these instances is a matter of the system not having enough complexity to support class four behavior, or (more likely according to NKS thinking) that it is just a limited sample size thing - 4s being rare in the 3+4 complex class combined, you need a sizable sample of complex rules to expect fours. They don't appear to be far off - typically one sees them at the same time or right after the 3s show up, just less of them. (E.g. there are already 4s in the ECAs). After that, you get a lot more 3s, but the simple portion never goes away completely. 4s never seem to dominate.

This is an inductive generalization, and might not hold for every sort of rule system. Some have coarser possible changes in their internal resources, so effectively the next class you can look at is well on in that typical sequence. Some have a lot less going on, and a lot more needs to be added before anything interesting appears. (Think of the difference between mobile automata with only a single active cell, and CAs which update in parallel each step). Some speculated that 4s occurred at the point of transition from simplicity to complexity, and "beyond" that one had 3s only. It is hard to sustain that idea consistently, though, because it requires notions of "nearer" that work inside systems with the same set up (at first sight, at the same point on the "more resources" dial). Where there are lots of 3s there will be 4s, is a safer way of putting it.

Then one has to remember that these classes are for typical behavior, that is, from most initial conditions. There are always sets of initial conditions for some rules that give behavior different from their typical behavior from random initials. 3s that act in simple ways when they have periodic initial conditions are the classic case of this. You are effectively getting many copies of their behavior from very narrow initial conditions over and over on the same pattern. More generally, a complex system can do simple things. You can program a universal computer to emulate a clock. (Universal implies programmable). If the algorithm it is emulating is simple enough, that simplicity will show up in aspects of its behavior, may be the most obvious or only thing going on, etc.

What should one then expect from empirical as opposed to formal systems? It depends on where on the more system resources dial you think it is plausible they will be. Lots of natural systems are going to be simple enough, with few enough components interacting in straightforward ways, that they are effectively on the low end of the formal scale. You should expect simple behavior, fixed points and periodic cycles. If you ask only for averages of various kinds you can find such simplicity even if the empirical system has lots of fine differences in other respects. So you should expect statistical regularities well after locally simple behavior "gives out". Formal characteristics like independence or linearity in this or that aspect are all many statistical theorems need to "go through".

If on the other hand the empirical system seems to have distinct components that interact in logical ways, without all cancelling out or accumulating independently, then NKS tells us to expect the typical spectrum of complex behaviors to show up rapidly. Meaning we should expect some regular cases, subsystems, or aspects still, but also others that are effectively random in the details (while statistically regular in suitable average measures of various kinds), and others - less common than the previous perhaps - that are effectively programmable.

Meaning, they will behave in ways so complicated and so dependent on details, that we can only tell what they will do by explicitly reproducing their own calculation step by step, or by watching how they behave empirically. We already have intuition about such systems, but they are perhaps more familiar from technology or human history than science. Also in experimental disciplines, to be sure, and in some evolutionary processes. What I am thinking of though are cases from history where we fall back on "thick description" of the details of events, or in technology things like economic prediction, or debugging a complicated computer program, where trial and error is our dominant method. You try something and see what it does, and try something else if you don't like the first outcome.

NKS tells us that this last form of behavior, programmable complexity, should be more common in natural systems with simple components, than we might have expected in the past. That such complexity is in no way restricted to artificial systems designed to have it as a property, or to systems that pass through unpredictable human actors, or to systems that are optimized survivors of lots of repeated trial and error. Complexity does not need those things to appear. It can happen already with very little in the way of intricate past history or formal resources. And it suggests we approach such systems with a toolkit drawn from experimental science, with formal experiment added, rather than expecting them to yield to purely deductive methods or "closed form" mathematical models.

I hope this helps.

Report this post to a moderator | IP: Logged

Registered: Jul 2004
Posts: 4

Jason,

You mention that universality implies programmability. Do you mean that any system with class 4 behavior (say rule 110) could be, in principle, programmable?

Is this implied by the Principle of Computational Equivalence?

Report this post to a moderator | IP: Logged

Registered: Aug 2003
Posts: 712

A system is universal if it can impliment any computation, for some arrangement of its inputs. That is, it needs to be able to mimic the behavior of an arbitrary Turing machine - that is the definition of universality. (If some TM can do it, we call it "a computation" - that is a definition). Since some universal systems simpler than the class "all Turing machines" are already known, though, the job of showing a given system is in fact universal is considerably simpler. You only have to show that it can emulate the behavior of any other known universal system for all of that (emulated) system's possible inputs.

So we get something of a "ratchet". The first universal TM construction had to show it could do anything any TM could do, even one with more head states or colors on the tape. Just slower, using more spaces on the tape in place of extra colors and the like. After that, one only needed to show some other system could emulate that TM, not all of them. Now that we have results like Rule 110, you only need to be able to emulate rule 110 for any inputs.

I say "programmability" a lot rather than "universality", because universality in the strict sense relies on (countable) infinities, in memory size (or running time, or both - there are ways to trade one for the other). Our practical computers do not have infinite memory. We design them to be universal if they did, and find they are as flexible as anything else we can think of. I am using the term "programmable" to descibe this finite flexibility, which passes to universality in the strict sense in the "any memory" limit. I want to make clear the sense of programmability I have in mind is the practical one that our computers have, not an infinity-requiring mathematical idealization.

You ask if all class 4s are programmable. PCE conjectures that they are, and it is widely believed by NKS researchers, but it is not proven. The reason it is widely believed is the aforementioned ratchet and experience in constructing general emulations. It is easy to make a CA (with plenty of colors) that mimics an arbitrary TM. It is much more complicated to show a cyclic tag system that can emulate a universal TM can in turn be emulated by rule 110. We see how much easier it is with more colors etc. And we now have the easier target, emulate 110 and you are there. There might conceivable be some special subclass of 4s with less computational ability than 110, but it seems implausible, since it has the minimum number of colors and the minimum range in which class 4 behavior shows up. Almost all 4s are going to have more "room" to be programmed than 110 does. That is the reason there is confidence about it, but showing it is formally true would be a real result. And it would be partial confirmation of PCE.

PCE goes on to make the much harder claim that even the 3s are programmable in principle, even if they are so much harder to actually control or understand, that we'd never pick them if we had a choice in the matter. If true, this claim would tell us something about lots of natural systems we now typically think of as "well mixed" and random, rather than programmable. PCE thinks complexity has one cause, universality, and that the 3s will be over its threshold. But that is not established yet and anybody might reasonably doubt it. This is called the class 3 problem - to show any class 3 system is universal, or conversely to establish that 3s cannot support universal computation - for some clear and systematic reason (uncontrolled information spread perhaps).

I hope this helps.

Report this post to a moderator | IP: Logged

Registered: Jul 2004
Posts: 4

Jason,

The sense of programmability I was talking about was in encoding. That is, a system is programmable if you can encode it -or program it- with some input or initial condition in such a way that you get an output that can be decoded in the same way.

So the question would be, given that a system is universal, is there always a way we can encode an input so that it can perform a certain computation? If that is the case, it would mean that the initial condition in rule 110 could, in principle, be encoded in different ways so that it could perform different kinds of computations. The same would apply with other class 4 systems (living systems perhaps), if PCE stands.

The other question would be: does universality imply a halting condition? That is, if you have a system that calculates something, the only way to know that the computation is complete is when the system halts? Wouldn't a final stationary state imply then a class 1 behavior?

I would appreciate you insights on these matters.

Report this post to a moderator | IP: Logged

Registered: Aug 2003
Posts: 712

"a system is programmable if you can encode it -or program it- with some input or initial condition in such a way that you get an output that can be decoded in the same way."

Well, the encoding scheme and the decoding scheme need not be the same as each other. But yes they can each be fixed for all the initial conditions, not rejiggered for each potential calculation. And then the space of initials of the underlying system impliment precisely the computable functions - in the infinite memory limit, anyway. (Some calculations in some encodings and rules, may require very large initials, etc). One can also require that the encoding and decoding schemes always halt, to prevent them from doing all the real work for you.

"given that a system is universal, is there always a way we can encode an input so that it can perform a certain computation?"

Yes, in principle. Where it is in the enumeration of initial conditions for the system and encoding you've picked, is another matter. And therefore how fast or efficient the computation will be in that system as opposed to some other.

A mapping that takes you from a function in a baseline universal system, typically one we understand well intuitively (e.g. arithmetic), to a translated construction (encoder, initial, decoder) in another system, is in effect a compiler. If the emulated system is close the compiler may be quite simple. Even if it isn't obviously close, but is abstract and dessicated enough, a quite simple compiler will often suffice.

Matthew Szudzick has given several examples in summer program lectures, e.g. a compiler for s-k combinators that shows how they can impliment any function in arithmetic. Tommaso Bolognesi at NKS SS 2005 showed a compiler for process algebras (an operator language akin to expression trees). It is often easier to show a direct emulation scheme for a closely related system e.g. the construction on page 658 that shows how a CA with plenty of allowed colors emulates any TM, using sets of colors to represent head positions and states, with a modded color value giving the state of the tape under the head. Page 786 shows a single integer equation in arthimetic (a diophantine equation) that encodes the behavior of rule 110. Any question about the behavior of rule 110 can be translated into a question about solutions to that equation. All of these are general translation schemes.

"the initial condition in rule 110 could, in principle, be encoded in different ways so that it could perform different kinds of computations."

That you can encode any computation in rule 110 is what the proof of 110's universality establishes. It gives a way of encoding states in cyclic tag systems in configurations in rule 110, using the various backgrounds and gliders naturally occurring in 110 as information elements. So that is effectively a compiler for cyclic tag computations to be executed by a rule 110 processor. Cyclic tag systems can in turn emulate arbitrary TMs according to a different scheme. So, given a TM to emulate, one can run it through a cyclic tag emulation scheme and get a cyclic tag system and initials set up that emulates that TM. Then one can compile that cyclic tag set up into a rule 110 set up. And then run rule 110, read out its output according to the decoding scheme the construction provides, and get an answer to the cyclic tag system's behavior from those initials. One can then translate that answer according to the decoding scheme of the cyclic tag system emulation of the TM, and recover a TM output from the initials specified.

Naturally, you'd never want to (lol). It would be hopelessly inefficient for practical purposes. But the space of computations reached is formally the same, since the possible computations can thus be put into one to one correspondance. That is the theoretical interest in the result. Also, there are plenty of theorems about the possible behaviors of universal systems which immediately "go through" as soon as one has established such a correspondance.

In a more practical context, you can think about writing functional computer programs in different higher level languages. You can write a program that behaves the same way - in an input to output pair sense - in lots of different ways, and in any higher level language. And you can write compilers for higher level languages that enable them to run on different machines, with different base instruction sets, etc. It is a similar point about behavior-preserving formal flexibility. Which is a threshold - once you are over it, the space of possible computations that can be reached (in the infinite memory, or infinite initial condition size limit, to be sure) is the same.

And the NKS point is that we can find instances of systems for which that is all true, that are so simple we can readily imagine even natural systems not designed for it, being past that flexibility threshold. It has been proven of some simple class 4s, and the relative ease of constructing new chains of emulation among 4s with more internal resources (more colors or longer range e.g.) leads Wolfram to expect, the 4s in general are all over this flexibility threshold. That has not been proven, but it is widely believed. More controversial and harder to see how to establish in any given case, is Wolfram's stronger conjecture, that even class 3s are over this threshold.

"does universality imply a halting condition?"

In general no. Decoding schemes have to be allowed to treat some states as answers, even if e.g. they contain patterns that remain but shift to the left forever, say. A decoding scheme itself can't run forever (i.e. it can't take forever to decide what the system it is supposedly decoding, is "saying" at time or step t), but it can return the answer "hasn't halted" about the system it is decoding. As for the behavior of the universal system itself, it cannot give a definite answer in finite time under a fixed decoding scheme for all inputs, or it would not be able to emulate e.g. a TM that fails to halt, so it would not be universal. All universal systems can (for some inputs, or "potentially") get into loops that might never end, that might depend on the outcome of some elaborate and incompressible sub-calculation, etc.

Fine questions by the way.

Report this post to a moderator | IP: Logged