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