FlameandFury wrote:I guess this'll be my first term project then: Finding a proof of universal computation. I know it's going to be hard, but it's going to be easier than actually making one, and I'm collecting useful slow salvos. I'm pretty sure I just need the proper PUSH, PULL, and FIRE reactions as well as a method to create more gliders, or am I wrong?
It sounds more like you're describing a
universal constructor than a
universal computer. You can easily have the second without the first. For example, in many rules you could build circuitry out of structures that it's impossible to either create or destroy.
However, as long as there are mechanisms available that can perform simple logic operations, even if they're Gardens of Eden that had to be there at T=0, most likely those mechanisms could still be arranged into a structure that can perform universal computations to make something programmable, equivalent to a Turing machine.
So if you do want a universal computer, you have a somewhat harder job than just finding PUSH, PULL, and FIRE mechanisms -- and you don't even really need those at all. Instead, you have to find some basic logic mechanisms and workable ways of stringing them together.
Conversely, if you want a universal constructor, you also have a somewhat harder job if you're working with a new rule. To show that a constructor is "universal", you have to somehow show that it's capable of constructing anything constructible.
-- Or at least you have to show that the constructor is capable of constructing a wide enough variety of objects that it could construct itself, with the proper programming, or an unlimited number of other configurations. Theoretically there might be weird not-quite-Garden-of-Eden patterns that are provably not constructible using the universal constructor, but _can_ be constructed by some other means -- crashing spaceships together that are themselves Gardens of Eden, perhaps.
That seems as if it would usually be a really strange degenerate case, however, and concrete examples are very hard to find.
So if the constructor can provably construct "almost everything", or even can just provably construct all the components that make up the constructor, many people consider that to be a demonstration of "universality" -- even if there does turn out to be some weird class of technically constructible things that it can't actually construct (!).