4 ms·

As a lay Comp Sci person I am wondering what this translates into? What implication does this have?

zorked 4y ago
It's pretty cool.
chriswarbo 4y ago
The principle is the same as von Neumann's "universal constructor", so it doesn't really prove anything we didn't know in theory. However, von Neumann's design uses a cellular-automaton with many more rules, and those were specifically chosen to help define that constructor (Langton Loops are a more extreme example of choosing rules to make construction easier). In constrast, the rules for Game of Life (GoL) were chosen to be simple and interesting, not fine-tuned for any particular patterns (for an even simpler set of rules, see the Rule 110 cellular-automaton). We know the GoL is Turing-complete, so it can emulate any computable system; including those other cellular-automata, e.g. von Neumann's universal constructor. Such emulations will typically use a large GoL pattern to represent each emulated cell (e.g. see "life in life"): if we emulate a universal constructor, we can use it to assemble any pattern of those emulated cells. We could also emulate GoL inside some other cellular-automaton, and hence use a universal constructor to assemble any pattern of emulated GoL cells. But the question still remains: can we assemble any pattern of "native" GoL cells? That's what the constructors in the article are doing (at least, for a broad class of patterns). The rest is a matter of "code golf", trying to make the patterns smaller and faster (and indeed feasible to run on a real PC!) https://en.wikipedia.org/wiki/Von_Neumann_universal_constructor https://en.wikipedia.org/wiki/Von_Neumann_universal_construc... https://en.wikipedia.org/wiki/Langton%27s_loops https://en.wikipedia.org/wiki/Langton%27s_loops https://en.wikipedia.org/wiki/Rule_110 https://en.wikipedia.org/wiki/Rule_110 https://conwaylife.com/wiki/Turing_machine https://conwaylife.com/wiki/Turing_machine https://conwaylife.com/wiki/Unit_cell https://conwaylife.com/wiki/Unit_cell

It's pretty cool.

The principle is the same as von Neumann's "universal constructor", so it doesn't really prove anything we didn't know in theory. However, von Neumann's design uses a cellular-automaton with many more rules, and those were specifically chosen to help define that constructor (Langton Loops are a more extreme example of choosing rules to make construction easier). In constrast, the rules for Game of Life (GoL) were chosen to be simple and interesting, not fine-tuned for any particular patterns (for an even simpler set of rules, see the Rule 110 cellular-automaton). We know the GoL is Turing-complete, so it can emulate any computable system; including those other cellular-automata, e.g. von Neumann's universal constructor. Such emulations will typically use a large GoL pattern to represent each emulated cell (e.g. see "life in life"): if we emulate a universal constructor, we can use it to assemble any pattern of those emulated cells. We could also emulate GoL inside some other cellular-automaton, and hence use a universal constructor to assemble any pattern of emulated GoL cells. But the question still remains: can we assemble any pattern of "native" GoL cells? That's what the constructors in the article are doing (at least, for a broad class of patterns). The rest is a matter of "code golf", trying to make the patterns smaller and faster (and indeed feasible to run on a real PC!) https://en.wikipedia.org/wiki/Von_Neumann_universal_constructor https://en.wikipedia.org/wiki/Von_Neumann_universal_construc... https://en.wikipedia.org/wiki/Langton%27s_loops https://en.wikipedia.org/wiki/Langton%27s_loops https://en.wikipedia.org/wiki/Rule_110 https://en.wikipedia.org/wiki/Rule_110 https://conwaylife.com/wiki/Turing_machine https://conwaylife.com/wiki/Turing_machine https://conwaylife.com/wiki/Unit_cell https://conwaylife.com/wiki/Unit_cell