Menu
I was recently reading about artificial life and came across the statement, "Conway’s Game of Life demonstrates enough complexity to be classified as a universal machine." I only had a rough understanding of what a universal machine is, and Wikipedia only brought me as close to understanding as Wikipedia ever does. I wonder if anyone could shed some light on this very sexy statement?
Conway's Game of Life seems, to me, to be a lovely distraction with some tremendous implications: I can't make the leap between that and calculator? Is that even the leap that I should be making?
807
This has the same computational power as a universal Turing machine, so the Game of Life is theoretically as powerful as any computer with unlimited memory and no time constraints; it is Turing complete.
Conway's Game contributed to the theory of cellular automatons, a fertile theory in computing sciences associated with John von Neumann. Conway's version of this theory is often seen as a decisive vindication of it, making the theory simpler and easier to apply.
A universal machine, also known as a universal Turing machine or UTM, is a Turing machine capable of simulating any other Turing machine. It was defined mathematically by Alonzo Church, who also invented the Lambda calculus.
A universal Turing machine can calculate any recursive function, decide any recursive language, and accept any recursively enumerable language.
Paul Rendell implemented a Turing machine in Life. Gliders represent signals, and interactions between them are gates and logic that together can create larger components which implement the Turing machine.
Basically, any automatic machinery that can implement AND, OR, and NOT can be combined together in complex enough ways to be Turing-complete. It's not a useful way to compute, but it meets the criteria.
99
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
