Undecidability in Conway's Game of Life

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.


I think this is shown in Wainwright, R. (1974). Life is universal! Winter Simulation Conference: Proceedings of the 7th conference on Winter simulation, 2:449–459, although I haven't actually looked at the article, just seen it referenced elsewhere.


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.