on whether given an initial pattern and another pattern, can the latter pattern ever appear from the initial one. Rule 110 - most questions involving can property "X" appear later is undecidable. The problem of determining whether a quantum mechanical system has a spectral gap. Determining whether a player has a winning strategy in a game of Magic: The Gathering. Planning in a partially observable Markov decision process. The problem of planning air travel from one destination to another, when fares are taken into account. See also Lists of problems List of unsolved problems Reduction (complexity) Notes Bibliography Appendix C includes impossibility of algorithms deciding if a grammar contains ambiguities, and impossibility of verifying program correctness by an algorithm as example of Halting Problem. Discusses intractability of problems with algorithms having exponential performance in Chapter 2, "Mathematical techniques for the analysis of algorithms." Discusses undecidability of the word problem for groups, and of various problems in topology. Further reading External links Discussion at MathOverflow Mathematics-related lists Lists of problems