Skip to main content
edited tags
Link
Source Link
Hans-Peter Stricker
  • 9.7k
  • 5
  • 54
  • 113

Undecidability in Conway's Game of Life

I strongly believe that - given the rules of Conway's Game of Life and an initial configuration - it is not decidable by a Turing Machine whether a given pattern will emerge, let alone as a stable pattern, be it static, moving, and/or rotating.

How can this be proven?

I guess, this kind of uncomputability would go far beyond the "simple" unpredictability of non-linear systems.