This might be a way to start going about proving it:

Conway's Game of Life is Turing complete: it is possible to simulate a universal turing machine within the Game of Life.

Deciding whether a Turing machine will halt or continue infinitely for an input is the "Halting Problem". It is not possible to have a general algorithm that decides the Halting Problem for all possible inputs to a Turing machine simulated on the Game of Life.

Thus the Halting Problem is also undecidable for arbitrary inputs on particular subsets of initial patterns on the Game of Life: specifically those which implement a Turing machine simulation.

It should be a small step from there to being able to say that there is no general pattern or algorithm for deciding the ultimate outcome of running Conway's Life on any arbitrary pattern, except by actually simulating the running of Conway's Life on that particular arbitrary pattern.

Thus there is no general algorithm for deciding the ultimate result of Life on an initial pattern or for deciding the halting pattern on an initial pattern, except for actually running the simulation.

And since there is no short-cut to simulating Conway's Life on a pattern, there is no algorithmic way to predict the outcome of Life on an initial pattern, thus it is not possible to decide the halting problem for Life.

10more comments