Skip to main content
2 of 2
Added my comment below sleepless' answer to my answer
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.

Peter Shor
  • 6.3k
  • 4
  • 55
  • 65