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.
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.