6 ms·

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

throwaway71271 2y ago
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 https://en.wikipedia.org/wiki/Rule_110
- Joel_Mckay 2y ago
  It gets even funnier, some folks implemented a version in geometry nodes within Blender. https://www.youtube.com/watch?v=iSoqddxoCl8 https://www.youtube.com/watch?v=iSoqddxoCl8 One could do all sorts of fun abstractions with the simulation data. =3
nomilk 2y ago
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-game-of-life-be-classified-as-a-universal-machine https://stackoverflow.com/questions/394957/why-can-conway-s-... [1] https://copy.sh/life/?pattern=TetrisOTCAMP.mc https://copy.sh/life/?pattern=TetrisOTCAMP.mc
- chunkyks 2y ago
  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...
- hcs 2y ago
  > 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.
  - AlotOfReading 2y ago
    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.
- OscarCunningham 2y ago
  Right. The principled way to interact with a GoL computer is to implement yourself in the game.
- FartyMcFarter 2y ago
  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).
MPSimmons 2y ago
it turns out it CAN play Doom. That's impressive

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 https://en.wikipedia.org/wiki/Rule_110

Joel_Mckay 2y ago
It gets even funnier, some folks implemented a version in geometry nodes within Blender. https://www.youtube.com/watch?v=iSoqddxoCl8 https://www.youtube.com/watch?v=iSoqddxoCl8 One could do all sorts of fun abstractions with the simulation data. =3

nomilk 2y ago

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-game-of-life-be-classified-as-a-universal-machine https://stackoverflow.com/questions/394957/why-can-conway-s-... [1] https://copy.sh/life/?pattern=TetrisOTCAMP.mc https://copy.sh/life/?pattern=TetrisOTCAMP.mc

chunkyks 2y ago
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...
hcs 2y ago
> 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.
- AlotOfReading 2y ago
  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.
OscarCunningham 2y ago
Right. The principled way to interact with a GoL computer is to implement yourself in the game.
FartyMcFarter 2y ago
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).

MPSimmons 2y ago

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