First off, Wolfram’s attempt to classify automata into four categories is flawed: it isn’t obvious that every cellular automata falls into one of those categories and not all the categories are even rigorously defined. Also the claim that not many other “definite class-4” automata were found is unhelpful. The ways that things can turn out to be Turing complete are often surprising and non-obvious (cf for example the word problem or Hilbert’s 10th problem.) So the claim that an automaton rule isn’t obviously Turing complete is extremely weak evidence that it isn’t.
The fact that 1D cellular automata are weak is both unsurprising and not good evidence for anything. From a Solomonoff perspective, adding in extra dimensions is pretty cheap (Tangent: one issue that I don’t fully understand is why we shouldn’t be deeply surprised by how few dimensions our universe seems to have. One of the strongest arguments for string theory that I’m aware of is that it answers this by saying that there really are more dimensions. However, string theory doesn’t really do a satisfactory job in that regard because the behavior of the individual dimensions is likely to vary, while the Occamian approach predicts that dimensions that are all treated the same way should be cheap.) But there are all the 2D automata and no one has even done almost any investigation of low dimensionsal automata for higher than 2. 3 and 4 dimensions would be the obvious ones where interesting things might happen. And there’s also been very little work at automata that uses a basic tiling form other than squares (e.g. equilateral triangles, or hexagons, or pairs of octagons and squares with possibly different rules for the two types.)
Incidentally, I suspect that most of the so-called “chaotic” cellular automata are Turing complete but simply feindishly difficult to establish as such.
There’s also an issue that’s relevant to all of this- whether or not an automata is Turing complete is not the same as the question as to whether or not it can support “life.” There are decent arguments for this claim, but it is far from obvious.
First off, Wolfram’s attempt to classify automata into four categories is flawed: it isn’t obvious that every cellular automata falls into one of those categories and not all the categories are even rigorously defined.
Without studying it in detail, I’m skeptical of the importance its claim. David says he has found class 1 and 3 systems that produce gliders. Perhaps David is poor at classifying systems. The existence of gliders strongly implies a system is class 2 or 4.
But perhaps he really has found class 1 and 3 systems in which a glider can exist. Is that important? Well, since the classification is statistical, being “class 1” really means “behavior is more class-1-like than any other class”. So particular structures can still exist in a class 1 or class 3 CA that exhibit a particular behavior. They’re just less-common.
I think Wolfram’s classifications are very well-defined as these things go (you can probably state them mathematically in terms of Lyapunov exponents, or number of attractors for finite worlds, or number of state transitions over time in Monte Carlo simulations, for instance). The problem is that the classification is statistical, so you can’t say “this is class 1 and therefore behavior X is impossible”.
The more important point, popping back up to the grandparent of this comment, is that I’m not convinced that the distribution of possible CAs resembles the distribution of possible physics.
Without studying it in detail, I’m skeptical of the importance its claim. David says he has found class 1 and 3 systems that produce gliders. Perhaps David is poor at classifying systems. The existence of gliders strongly implies a system is class 2 or 4.
But perhaps he really has found class 1 and 3 systems in which a glider can exist. Is that important? Well, since the classification is statistical, being “class 1” really means “behavior is more class-1-like than any other class”. So particular structures can still exist in a class 1 or class 3 CA that exhibit a particular behavior. They’re just less-common.
It’s the second paragraph that’s right here, I believe.
I generally agree with Epstein’s comments. Except that in his classification scheme, I tend to regard the “Contraction impossible.” case as pretty similar to the “Expansion impossible” case.
I think a major point of interest of Wolfram’s classification is that is suggested that universal automata were in class 4. If that is more false than true, the classification scheme loses much of its interest.
Incidentally, I suspect that most of the so-called “chaotic” cellular automata are Turing complete but simply feindishly difficult to establish as such.
Maybe. It is a fun speculation—but I don’t think anyone really knows. Rule 30 is an obvious test case. If that ever gets proved to be universal, the conjecture would become quite a bit more plausible.
If so, more automata would be lively. My speculation is partly based on “most” automata exhibiting chaotic dynamics, which don’t obviously support life or universal computation—because everything explodes.
There’s also an issue that’s relevant to all of this- whether or not an automata is Turing complete is not the same as the question as to whether or not it can support “life.” There are decent arguments for this claim, but it is far from obvious.
If you are Turing complete you can simulate anything—including arbitrary living systems.
...and if you aren’t Turing complete, the dynamics are usually pretty limited. Surely these two things are really the same thing.
If you are Turing complete you can simulate anything—including arbitrary living systems.
...and if you aren’t Turing complete, the dynamics are usually pretty limited. Surely these two things are really the same thing.
No. They aren’t. First at the most basic level you have that many would argue that simulating isn’t the same thing as actually being (many on LW would consider this to be wrong or so incoherent to not even be wrong and I’m inclined to sympathize with that view but it is something that needs to be considered). More seriously, just because the rule system is capable of simulating Turing machines when one can control the initial configuration doesn’t mean that any given universe actually will have that happen for a fixed configuration. For example, consider Conway’s Life. This is Turing complete in the strong sense that we have a computable map that takes Turing machines to Life configurations such that 1) the corresponding Life configuration will will form a stable non-empty configuration iff the Turing machine halts in an accepting state and 2) the corresponding Life configuration will die-off iff the Turing machine halts in an a rejecting state. But, and this is an important but, if we start with some Life configuration it won’t necessarily run through all or any interesting Turing machines. For example, the universe might obey Conway’s laws but have all squares start empty, or one that starts with a handful of live cells that quickly die.
Another problem is that one can conceive of (although I’m not aware of any known examples) of a set of cellular automata rules that allow something looks like “life” to occur (growing, dieing, reproducing, competing) but is too weak to be Turing complete.
Note also that being Turing complete doesn’t mean you can simulate anything- it means you can simulate anything in our universe. Universes that obey drastically different laws of physics are not necessarily Turing computable (so for example the HPMR world would be difficult for a Turing machine to handle due to the time-travel issues.) One can give even more straightforward examples, such as a universe identical to ours except that there’s a little black box that when fed a description of a Turing machine in some simple method will output a certain signal iff that Turing machine runs on the blank tape. The fact that our universe doesn’t do anything like that is essentially an empirical statement, not a statement about all universes (although there are plausibility arguments to think that all universes might behave this way. This is one issue that comes up when discussing weakened versions of the Tegmark ensemble.).
The upshot is that asking at whether or not a given cellular automata rule is Turing complete is not necessarily the same as asking whether or not that rule can support life.
“many would argue that simulating isn’t the same thing as actually being”
A useless and pointless argument, IMO. Patternism is a better philosophy. Artificial life is really alive.
“More seriously, just because the rule system is capable of simulating Turing machines when one can control the initial configuration doesn’t mean that any given universe actually will have that happen for a fixed configuration.”
The claim would be something like: living systems are Turing complete and Turing complete systems are capable of supporting life. I don’t think what you said impacts on that claim.
Another problem is that one can conceive of (although I’m not aware of any known examples) of a set of cellular automata rules that allow something looks like “life” to occur (growing, dieing, reproducing, competing) but is too weak to be Turing complete.
Yes, maybe. This seems like a pretty rare and esoteric possibility to me—but I wouldn’t say it was impossible.
If you define life as having anything to do with constructive evolution and adaptations, though, then I am going to have to ask for an example.
Note also that being Turing complete doesn’t mean you can simulate anything- it means you can simulate anything in our universe.
Noted—but that doesn’t seem to have much to do with life.
A useless and pointless argument, IMO. Patternism is a better philosophy. Artificial life is really alive.
I’d be inclined to agree that patternism is more coherent. But that doesn’t make the argument useless or pointless (indeed it is a pretty pointed issue since it matters a lot in this context).
Yes, maybe. This seems like a pretty rare and esoteric possibility to me—but I wouldn’t say it was impossible.
If you define life as having anything to do with constructive evolution and adaptations, though, then I am going to have to ask for an example.
Well, Sniffnoy has already pointed out the finite computation limit. But the following is an almost example. (Note that this example is not completely deterministic and allows arbitrarily many states in cells although any fixed configuration has only finitely many such in use.) Example: Cells can have any non-negative integer in them (with zero representing the empty cell): In any given iterarion, for any cell , there is a (1-1/(k+1))/2 chance that the cell is filled with k, where k is the largest number in an adjacent cell, and a ( (1-1/(k+1))/2) chance that it will fill with k+1. Now, start this with a single cell with k=1 and all others empty. The population will rapidly expand, and “evolve” towards higher and higher integers, expanding rapidly from the initial point, with different populations of integers expanding outwards and competing. One could make more complicated versions of this to allow more complicated adaptions (say giving a slight benefit to primes to preserve their current value rather than be overwritten). This would deal with the fact that this model doesn’t allow any interesting evolution (and indeed the ladder nature of the evolution in question makes it a very poor model, almost reflecting certain common misconceptions about evolution somehow being progressive.)
Note also that being Turing complete doesn’t mean you can simulate anything- it means you can simulate anything in our universe.
Noted—but that doesn’t seem to have much to do with life.
Right, I was bringing this up because you made a comment about Turing machines simulating anything.
Also note that a universe based on real numbers could reasonably have life and could not be simulated by a Turing machine but only a Blum-Shub-Smale machine.
Cells can have any non-negative integer in them (with zero representing the empty cell): In any given iterarion, for any cell , there is a (1-1/(k+1))/2 chance that the cell is filled with k, where k is the largest number in an adjacent cell, and a ( (1-1/(k+1))/2) chance that it will fill with k+1. Now, start this with a single cell with k=1 and all others empty. The population will rapidly expand, and “evolve” towards higher and higher integers, expanding rapidly from the initial point, with different populations of integers expanding outwards and competing.
Hmm. Yes. That meets my criteria for adaptation.
It’s pretty simple—I shoulda thought of that myself, and saved you some time.
Another problem is that one can conceive of (although I’m not aware of any known examples) of a set of cellular automata rules that allow something looks like “life” to occur (growing, dieing, reproducing, competing) but is too weak to be Turing complete.
Yes, maybe. This seems like a pretty rare and esoteric possibility to me—but I wouldn’t say it was impossible.
How about a really large finite state machine? While important theoretically, for the purposes we’re discussing, I don’t think we should need the infinitude of a Turing machine.
Right—I don’t literally mean to imply infinity. I just mean in the way that partial recursive functions can perform arbitrary computations (memory permitting) - or lambda calculus, or cellular automata.
First off, Wolfram’s attempt to classify automata into four categories is flawed: it isn’t obvious that every cellular automata falls into one of those categories and not all the categories are even rigorously defined. Also the claim that not many other “definite class-4” automata were found is unhelpful. The ways that things can turn out to be Turing complete are often surprising and non-obvious (cf for example the word problem or Hilbert’s 10th problem.) So the claim that an automaton rule isn’t obviously Turing complete is extremely weak evidence that it isn’t.
The fact that 1D cellular automata are weak is both unsurprising and not good evidence for anything. From a Solomonoff perspective, adding in extra dimensions is pretty cheap (Tangent: one issue that I don’t fully understand is why we shouldn’t be deeply surprised by how few dimensions our universe seems to have. One of the strongest arguments for string theory that I’m aware of is that it answers this by saying that there really are more dimensions. However, string theory doesn’t really do a satisfactory job in that regard because the behavior of the individual dimensions is likely to vary, while the Occamian approach predicts that dimensions that are all treated the same way should be cheap.) But there are all the 2D automata and no one has even done almost any investigation of low dimensionsal automata for higher than 2. 3 and 4 dimensions would be the obvious ones where interesting things might happen. And there’s also been very little work at automata that uses a basic tiling form other than squares (e.g. equilateral triangles, or hexagons, or pairs of octagons and squares with possibly different rules for the two types.)
Incidentally, I suspect that most of the so-called “chaotic” cellular automata are Turing complete but simply feindishly difficult to establish as such.
There’s also an issue that’s relevant to all of this- whether or not an automata is Turing complete is not the same as the question as to whether or not it can support “life.” There are decent arguments for this claim, but it is far from obvious.
Yes, David has a page about that topic.
Without studying it in detail, I’m skeptical of the importance its claim. David says he has found class 1 and 3 systems that produce gliders. Perhaps David is poor at classifying systems. The existence of gliders strongly implies a system is class 2 or 4.
But perhaps he really has found class 1 and 3 systems in which a glider can exist. Is that important? Well, since the classification is statistical, being “class 1” really means “behavior is more class-1-like than any other class”. So particular structures can still exist in a class 1 or class 3 CA that exhibit a particular behavior. They’re just less-common.
I think Wolfram’s classifications are very well-defined as these things go (you can probably state them mathematically in terms of Lyapunov exponents, or number of attractors for finite worlds, or number of state transitions over time in Monte Carlo simulations, for instance). The problem is that the classification is statistical, so you can’t say “this is class 1 and therefore behavior X is impossible”.
The more important point, popping back up to the grandparent of this comment, is that I’m not convinced that the distribution of possible CAs resembles the distribution of possible physics.
It’s the second paragraph that’s right here, I believe.
I generally agree with Epstein’s comments. Except that in his classification scheme, I tend to regard the “Contraction impossible.” case as pretty similar to the “Expansion impossible” case.
I think a major point of interest of Wolfram’s classification is that is suggested that universal automata were in class 4. If that is more false than true, the classification scheme loses much of its interest.
Maybe. It is a fun speculation—but I don’t think anyone really knows. Rule 30 is an obvious test case. If that ever gets proved to be universal, the conjecture would become quite a bit more plausible.
If so, more automata would be lively. My speculation is partly based on “most” automata exhibiting chaotic dynamics, which don’t obviously support life or universal computation—because everything explodes.
If you are Turing complete you can simulate anything—including arbitrary living systems.
...and if you aren’t Turing complete, the dynamics are usually pretty limited. Surely these two things are really the same thing.
No. They aren’t. First at the most basic level you have that many would argue that simulating isn’t the same thing as actually being (many on LW would consider this to be wrong or so incoherent to not even be wrong and I’m inclined to sympathize with that view but it is something that needs to be considered). More seriously, just because the rule system is capable of simulating Turing machines when one can control the initial configuration doesn’t mean that any given universe actually will have that happen for a fixed configuration. For example, consider Conway’s Life. This is Turing complete in the strong sense that we have a computable map that takes Turing machines to Life configurations such that 1) the corresponding Life configuration will will form a stable non-empty configuration iff the Turing machine halts in an accepting state and 2) the corresponding Life configuration will die-off iff the Turing machine halts in an a rejecting state. But, and this is an important but, if we start with some Life configuration it won’t necessarily run through all or any interesting Turing machines. For example, the universe might obey Conway’s laws but have all squares start empty, or one that starts with a handful of live cells that quickly die.
Another problem is that one can conceive of (although I’m not aware of any known examples) of a set of cellular automata rules that allow something looks like “life” to occur (growing, dieing, reproducing, competing) but is too weak to be Turing complete.
Note also that being Turing complete doesn’t mean you can simulate anything- it means you can simulate anything in our universe. Universes that obey drastically different laws of physics are not necessarily Turing computable (so for example the HPMR world would be difficult for a Turing machine to handle due to the time-travel issues.) One can give even more straightforward examples, such as a universe identical to ours except that there’s a little black box that when fed a description of a Turing machine in some simple method will output a certain signal iff that Turing machine runs on the blank tape. The fact that our universe doesn’t do anything like that is essentially an empirical statement, not a statement about all universes (although there are plausibility arguments to think that all universes might behave this way. This is one issue that comes up when discussing weakened versions of the Tegmark ensemble.).
The upshot is that asking at whether or not a given cellular automata rule is Turing complete is not necessarily the same as asking whether or not that rule can support life.
You make several points:
A useless and pointless argument, IMO. Patternism is a better philosophy. Artificial life is really alive.
The claim would be something like: living systems are Turing complete and Turing complete systems are capable of supporting life. I don’t think what you said impacts on that claim.
Yes, maybe. This seems like a pretty rare and esoteric possibility to me—but I wouldn’t say it was impossible.
If you define life as having anything to do with constructive evolution and adaptations, though, then I am going to have to ask for an example.
Noted—but that doesn’t seem to have much to do with life.
I’d be inclined to agree that patternism is more coherent. But that doesn’t make the argument useless or pointless (indeed it is a pretty pointed issue since it matters a lot in this context).
Well, Sniffnoy has already pointed out the finite computation limit. But the following is an almost example. (Note that this example is not completely deterministic and allows arbitrarily many states in cells although any fixed configuration has only finitely many such in use.) Example: Cells can have any non-negative integer in them (with zero representing the empty cell): In any given iterarion, for any cell , there is a (1-1/(k+1))/2 chance that the cell is filled with k, where k is the largest number in an adjacent cell, and a ( (1-1/(k+1))/2) chance that it will fill with k+1. Now, start this with a single cell with k=1 and all others empty. The population will rapidly expand, and “evolve” towards higher and higher integers, expanding rapidly from the initial point, with different populations of integers expanding outwards and competing. One could make more complicated versions of this to allow more complicated adaptions (say giving a slight benefit to primes to preserve their current value rather than be overwritten). This would deal with the fact that this model doesn’t allow any interesting evolution (and indeed the ladder nature of the evolution in question makes it a very poor model, almost reflecting certain common misconceptions about evolution somehow being progressive.)
Right, I was bringing this up because you made a comment about Turing machines simulating anything.
Also note that a universe based on real numbers could reasonably have life and could not be simulated by a Turing machine but only a Blum-Shub-Smale machine.
Hmm. Yes. That meets my criteria for adaptation.
It’s pretty simple—I shoulda thought of that myself, and saved you some time.
How about a really large finite state machine? While important theoretically, for the purposes we’re discussing, I don’t think we should need the infinitude of a Turing machine.
Right—I don’t literally mean to imply infinity. I just mean in the way that partial recursive functions can perform arbitrary computations (memory permitting) - or lambda calculus, or cellular automata.
So: a substrate capable of universal computation if it were extended to infinity.