computability-theoryds.dynamical-systems
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.
Here is a proof based on the recursion theorem, rather than a reduction of an undecidable problem.
Rice's Theorem. Suppose that $P$ is any set of computable functions, which is not empty and not all computable functions. Then the set $\{ e\mid \varphi_e\in P\}$ is not decidable, where $\varphi_e$ is the function computed by program $e$.
In other words, there is no general procedure to determine from a program whether the function it computes has property $P$ or not.
Proof. Suppose that the set were decidable. Fix a computable function $f$ that is in $P$, and another computable function $g$ that is not in $P$. Now, for any program $e$, let $h(e)$ be the program that on input $n$ first determines whether $\varphi_e\in P$; if so, it outputs $g(n)$, and otherwise $f(n)$. So $\varphi_{h(e)}$ is either $g$ or $f$, depending on whether $\varphi_e\in P$ or not, respectively (but note that we are using the opposite function). In particular, we'll have $$\varphi_e\in P\quad\iff\quad\varphi_{h(e)}\notin P.$$ Meanwhile, by the recursion theorem, there is a program $e$ such that $\varphi_e=\varphi_{h(e)}$, which now gives an immediate contradiction, since $\varphi_e$ and $\varphi_{h(e)}$ are supposed to be opposite with respect to $P$. QED
Just to help develop intuition - here is a fragment of a typical evolution for large $n$ (made with Golly)
Best Answer
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.