Hacker News new | past | comments | ask | show | jobs | submit login

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



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

https://en.wikipedia.org/wiki/Langton%27s_loops

https://en.wikipedia.org/wiki/Rule_110

https://conwaylife.com/wiki/Turing_machine

https://conwaylife.com/wiki/Unit_cell


It's pretty cool.




Consider applying for YC's W25 batch! Applications are open till Nov 12.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: