Proof that Conway's Game of Life's outcome is impossible to calculate

Question

I know that it is impossible to know whether or not a starting pattern for the Game of Life will exist/destroy itself as iterations approach infinity. However, I haven't seen a proof of this. What is the proof of this claim?

Well, I imagine one shows that Life is a Universal Turing Machine and then invokes the Halting Problem. — lulu, Nov 23 '22 at 19:34

score 1 · Accepted Answer · answered Nov 23 '22 at 19:41

First, note that the Game of Life is Turing complete. In other words, it can simulate any Turing machine.

Second, note that whether the game ends or continues ad infinitum is analogous to whether there exists a general algorithm that will determine if any program will halt. Of course, the answer is that no such general algorithm exists. This is known as the Halting Problem.

Thus, there is no general algorithm that can determine whether or not the Game of Life will end or continue ad infinitum.

Using the verb "note" is quite the understatement... – Mariano Suárez-Álvarez Nov 23 '22 at 20:00 — Mariano Suárez-Álvarez, Nov 23 '22 at 20:00

Proof that Conway's Game of Life's outcome is impossible to calculate

1 Answers1