Timeline for Undecidability in Conway's Game of Life
Current License: CC BY-SA 2.5
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 11, 2010 at 1:27 | history | edited | sleepless in beantown | CC BY-SA 2.5 |
spelling correction "simulation" fixed
|
| Nov 9, 2010 at 3:30 | history | edited | sleepless in beantown | CC BY-SA 2.5 |
edited out redundant verbiage used overly wordage
|
| Nov 9, 2010 at 0:46 | comment | added | Peter Shor | 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. | |
| Nov 9, 2010 at 0:25 | comment | added | sleepless in beantown | @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. | |
| Nov 9, 2010 at 0:12 | comment | added | Hans-Peter Stricker | 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? | |
| Nov 9, 2010 at 0:09 | history | edited | sleepless in beantown | CC BY-SA 2.5 |
added result to the first few steps
|
| Nov 9, 2010 at 0:01 | history | answered | sleepless in beantown | CC BY-SA 2.5 |