12
$\begingroup$

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.

Improve this question
$\endgroup$
15
  • 1
    $\begingroup$ That is probably true, but it is not clear how to prove it and why (it may require substantial effort). $\endgroup$
    – Steve Richards
    Commented Nov 8, 2010 at 23:45
  • 1
    $\begingroup$ Why "why"? It would be a clear-cut case, why the future - e.g. of evolution - cannot be foreseen in principle. $\endgroup$
    – Hans-Peter Stricker
    Commented Nov 8, 2010 at 23:47
  • 2
    $\begingroup$ @Hans: The name "life" does not really mean it is a simulation of real life. Certainly there are undecidable algorithmic problems which are closer to real evolution than Conway's game. $\endgroup$
    – Steve Richards
    Commented Nov 8, 2010 at 23:50
  • 1
    $\begingroup$ @Hans: Yes, that is what I meant. Halting problem is also about formation of pattern, only the patterns are 1-dimensional. I think the popularity of Convay's game is due to its name not due to its simplicity. If you call Turing machine "Life and/or death" machine, it would be much more popular too. :) $\endgroup$
    – Steve Richards
    Commented Nov 9, 2010 at 0:24
  • 1
    $\begingroup$ @Hans: It depends on the interpretation. If $f$ is the halting state, then the problem is where $f$ will ever appear. So $f$ is the pattern. You can view words as multi-colored intervals. A move is a re-coloring of a certain small subinterval according to some finite collection of rules, and the problem is whether a certain color or combination of colors will ever appear. You can always assume that there are only two colors only. That's 1-dimensional "life". $\endgroup$
    – Steve Richards
    Commented Nov 9, 2010 at 0:38

4 Answers 4

Reset to default
40
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Accepted for the comment on sleepless' answer! $\endgroup$
    – Hans-Peter Stricker
    Commented Nov 9, 2010 at 0:49
  • 3
    $\begingroup$ Is this the lesson to be learned: The possible emergence of a pattern in a cellular automaton with a given initial pattern is undecidable iff the automaton is complex enough to be able to simulate a universal Turing Machine? $\endgroup$
    – Hans-Peter Stricker
    Commented Nov 9, 2010 at 9:25
  • 3
    $\begingroup$ Yes, that's the lesson to be learned. $\endgroup$
    – John Baez
    Commented Nov 9, 2010 at 9:27
  • $\begingroup$ I added my comment on sleepless's answer to my answer, making it more self-contained. $\endgroup$
    – Peter Shor
    Commented Oct 28, 2019 at 14:12
8
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ +1 for knowing the original reference! I remember reading about the Turing completeness of Life, but could not recall or find a link for where it was originally stated and/or proven . Thanks, Alex. Now, off to the hunt for a link to an online version of these proceedings from the caveman-ARPAnet days of computer science... Let me know if you know where to find it. It probably exists on cellulose somewhere. $\endgroup$
    – sleepless in beantown
    Commented Nov 9, 2010 at 0:21
  • 1
    $\begingroup$ Unfortunately, I don't have it in electronic form, so maybe you can post the link here if your hunt is successful. $\endgroup$
    – Alex B.
    Commented Nov 9, 2010 at 0:28
  • $\begingroup$ One link is here dx.doi.org/10.1145/800290.811303 but you need a subscription to get the full text. How complete is this proof? My impression is that fully fleshed-out proofs of the universality of Life didn't appear until much more recently than 1974. $\endgroup$
    – Timothy Chow
    Commented Nov 9, 2010 at 17:02
8
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ What is hard to see for me are the intermediate steps from my original question: Given that Conway's Game of Life is Turing complete, how does it follow that the emergence of a given pattern cannot be decided? (Two or three intermediate steps would be welcome!) Or is it all obvious? $\endgroup$
    – Hans-Peter Stricker
    Commented Nov 9, 2010 at 0:12
  • 1
    $\begingroup$ @Hans-Stricker, There is no extra middle step. $$ $$ Conway's Life is equivalent to a Turing machine since it is Turing complete, thus the Halting Problem applies equally well to any pattern on Conway's Life. The only way to decide a halting problem is by actually running the simulation: there are no shortcuts for simulating a Turing complete system. Pretty much there is no middle step between showing that a system is Turing Complete and being able to deduce that the Halting Problem is undecidable for it, as Peter Shor says in his answer and comments. $\endgroup$
    – sleepless in beantown
    Commented Nov 9, 2010 at 0:25
  • 7
    $\begingroup$ You can program the 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. $\endgroup$
    – Peter Shor
    Commented Nov 9, 2010 at 0:46
5
$\begingroup$

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, Winning Ways for your Mathematical Plays. Academic Press, 1982]

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ The argument in the book, though very nice, it is not really enough to be fleshed out into a full proof without significant additional work beyond what is indicated there (I have lectured on the topic a few times). $\endgroup$
    – Andrés E. Caicedo
    Commented Nov 9, 2010 at 2:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .