most recent 30 from http://mathoverflow.net 2013-05-25T09:21:39Z http://mathoverflow.net/feeds/question/45378 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/45378/undecidability-in-conways-game-of-life Hans Stricker 2010-11-08T23:40:27Z 2010-11-11T01:27:18Z

<p>I strongly believe that - given the rules of Conway's <a href="http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life" rel="nofollow">Game of Life</a> 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.</p> <blockquote> <p>How can this be proven?</p> </blockquote> <p>I guess, this kind of uncomputability would go far beyond the "simple" unpredictability of non-linear systems.</p>

http://mathoverflow.net/questions/45378/undecidability-in-conways-game-of-life/45381#45381 sleepless in beantown 2010-11-09T00:01:26Z 2010-11-11T01:27:18Z

<p>This might be a way to start going about proving it:</p> <p>Conway's Game of Life is <a href="http://en.wikipedia.org/wiki/Turing_complete" rel="nofollow">Turing complete</a>: it is possible to simulate a universal turing machine within the Game of Life.</p> <p>Deciding whether a Turing machine will halt or continue infinitely for an input is the <a href="http://en.wikipedia.org/wiki/Halting_problem" rel="nofollow">"Halting Problem"</a>. 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. </p> <p>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. </p> <p>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.</p> <p>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.</p> <p>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.</p>

http://mathoverflow.net/questions/45378/undecidability-in-conways-game-of-life/45382#45382 Peter Shor 2010-11-09T00:02:33Z 2010-11-09T00:02:33Z

<p>Conway's game of Life <a href="http://rendell-attic.org/gol/tm.htm" rel="nofollow">can simulate a universal Turing machine</a> which means that it is indeed undecidable by reduction from the halting problem. </p>

http://mathoverflow.net/questions/45378/undecidability-in-conways-game-of-life/45384#45384 Alex Bartel 2010-11-09T00:05:00Z 2010-11-09T00:05:00Z

<p>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.</p>

http://mathoverflow.net/questions/45378/undecidability-in-conways-game-of-life/45388#45388 Mariano Suárez-Alvarez 2010-11-09T00:56:36Z 2010-11-09T00:56:36Z

<p>This is proved (or, really, a sketch of the proof is given) in the second volume of the extraordinary [Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy, <em>Winning Ways for your Mathematical Plays.</em> Academic Press, 1982]</p>