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

TIL that Conway's game is turing complete. Wow.



then you will be even more impressed by Rule 110 being turing complete with a specific background pattern.

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


It gets even funnier, some folks implemented a version in geometry nodes within Blender.

https://www.youtube.com/watch?v=iSoqddxoCl8

One could do all sorts of fun abstractions with the simulation data. =3


Struggling to wrap my head around how this is possible. Seems others are too [0]. A computer made in, say, minecraft can be given inputs. But since GoL is a zero player game (the player only selects the initial states), how can it possibly compute anything other than the static inputs it's originally provided? Perhaps that's sufficient for Turing Completeness? (when I click 'Run' on the provided link, my chrome tab becomes unresponsive; was hoping to disprove my own disbelief by playing Tetris in GoL but thus far unsuccessful, yet remaining hopeful!).

[0] https://stackoverflow.com/questions/394957/why-can-conway-s-...

[1] https://copy.sh/life/?pattern=TetrisOTCAMP.mc


> how can it possibly compute anything other than the static inputs it's originally provided? Perhaps that's sufficient for Turing Completeness?

Yes, the basic Turing machine model isn't "interactive", it takes some initial input and runs from there.

Edit: Maybe a better way of putting this:

Since you can build a Turing machine as a GoL pattern that will interact with another pattern (its input), analysis of GoL patterns includes analysis of Turing machines, generally.


The basic Turing machine model isn't interactive, but Turing also discussed "choice" machines that were. They're a variant of what we now call non-deterministic turing machines where the decision is determined by a human oracle instead of some other method.


If you think about it, a Turing machine is also Turing complete, and also is a zero player game where one only sets initial inputs...


Game of life is no different from other computers in this regard. You can make it have no inputs (just disconnect your mouse/keyboard in the case of your computer), or you can make it have inputs (just have a few GoL cells be controlled externally).


Right. The principled way to interact with a GoL computer is to implement yourself in the game.


it turns out it CAN play Doom. That's impressive




Consider applying for YC's Spring batch! Applications are open till Feb 11.

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

Search: