Skip to main content
Added my comment below sleepless' answer to my answer
Source Link
Peter Shor
  • 6.3k
  • 4
  • 55
  • 65

Conway's game of Life can simulate a universal Turing machine which means that it is indeed undecidable by reduction from the halting problem.

You can program this Turing machine in the game of Life so that it builds some pattern when it halts that doesn't occur while it's still running. Then the pattern will be built if and only if the Turing machine halts.

Conway's game of Life can simulate a universal Turing machine which means that it is indeed undecidable by reduction from the halting problem.

Conway's game of Life can simulate a universal Turing machine which means that it is indeed undecidable by reduction from the halting problem.

You can program this Turing machine in the game of Life so that it builds some pattern when it halts that doesn't occur while it's still running. Then the pattern will be built if and only if the Turing machine halts.

Source Link
Peter Shor
  • 6.3k
  • 4
  • 55
  • 65

Conway's game of Life can simulate a universal Turing machine which means that it is indeed undecidable by reduction from the halting problem.