Timeline for Undecidability in Conway's Game of Life
Current License: CC BY-SA 2.5
22 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 9, 2010 at 1:10 | history | edited | Mariano Suárez-Álvarez |
edited tags
|
|
| Nov 9, 2010 at 1:09 | comment | added | Mariano Suárez-Álvarez | Hmm. "integrable systems" has a technical meaning rather different from that. Retagging... | |
| Nov 9, 2010 at 1:06 | comment | added | Hans-Peter Stricker | @Mariano: integrable = solvable = computable = decidable. If you find this tag inappropriate, please feel free to remove it. | |
| Nov 9, 2010 at 0:59 | comment | added | Mariano Suárez-Álvarez | What is the connection to integrable systems?! | |
| Nov 9, 2010 at 0:56 | answer | added | Mariano Suárez-Álvarez | timeline score: 5 | |
| Nov 9, 2010 at 0:49 | vote | accept | Hans-Peter Stricker | ||
| Nov 9, 2010 at 0:41 | comment | added | Hans-Peter Stricker | @Steve: Thanks, that's enlightening. Have to think the Halting Problem over. | |
| Nov 9, 2010 at 0:38 | comment | added | Steve Richards | @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". | |
| Nov 9, 2010 at 0:28 | comment | added | Hans-Peter Stricker | @Steve: I would have guessed that the patterns of the Halting problem are 0-dimensional: "Stop and/or go". | |
| Nov 9, 2010 at 0:24 | comment | added | Steve Richards | @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. :) | |
| Nov 9, 2010 at 0:19 | comment | added | Hans-Peter Stricker | @Steve: Now I understand what you have meant: Conway's game is just another undecidable problem, not more relevant to "life" than the Halting problem. You may be right. Anyway: Conway's game concerns the formation of patterns in a very graspable sense. | |
| Nov 9, 2010 at 0:14 | comment | added | Hans-Peter Stricker | @Peter: I have seen this, too. But it didn't give me a clue how to answer my question. (Please see my comment to sleepless in beantown's answer.) | |
| Nov 9, 2010 at 0:05 | answer | added | Alex B. | timeline score: 8 | |
| Nov 9, 2010 at 0:03 | comment | added | Steve Richards | Halting problem, for example. Consider a sequence of substitutions $u_i\to v_i$, where $u_i, v_i$ are words. Start with a word $w$. Question: will a certain letter $f$ appear in any word obtained after a series of substitutions. There are very few substitution rules needed (three, I believe, perhaps even 2) to get undecidability. | |
| Nov 9, 2010 at 0:02 | answer | added | Peter Shor | timeline score: 40 | |
| Nov 9, 2010 at 0:01 | answer | added | sleepless in beantown | timeline score: 8 | |
| Nov 8, 2010 at 23:54 | comment | added | Hans-Peter Stricker | But maybe you can give me a hint, where comparable questions have been answered already? | |
| Nov 8, 2010 at 23:53 | comment | added | Hans-Peter Stricker | But I guess there won't be undecidable algorithmic problems that are considerably simpler than Conway's game. | |
| Nov 8, 2010 at 23:50 | comment | added | Steve Richards | @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. | |
| Nov 8, 2010 at 23:47 | comment | added | Hans-Peter Stricker | Why "why"? It would be a clear-cut case, why the future - e.g. of evolution - cannot be foreseen in principle. | |
| Nov 8, 2010 at 23:45 | comment | added | Steve Richards | That is probably true, but it is not clear how to prove it and why (it may require substantial effort). | |
| Nov 8, 2010 at 23:40 | history | asked | Hans-Peter Stricker | CC BY-SA 2.5 |