List of undecidable problems

In computability theory, an undecidable problem is a problem whose language is not a recursive set. More informally, such problems cannot be solved in general by computers; see decidability. This is a list of undecidable problems. Note that there are uncountably many undecidable problems, so this list is necessarily incomplete. Though undecidable languages are not recursive languages, they may be a subset of Turing recognizable languages.

Problems related to logic

* Type inference and type checking for the second-order lambda calculus (or equivalent). [J. B. Wells. [http://citeseer.ist.psu.edu/article/wells96typability.html "Typability and type checking in the second-order lambda-calculus are equivalent and undecidable."] Tech. Rep. 93-011, Comput. Sci. Dept., Boston Univ., 1993.]

Problems related to abstract machines

* The halting problem (determining whether a Turing machine (or equivalent) halts or runs forever).
* The busy beaver problem (determining the length of the longest halting computation among machines of a specified size).
* Rice's theorem states that for all non-trivial properties of partial functions, it is undecidable whether a machine computes a partial function with that property.

Other problems

* The Post correspondence problem.
* The word problem for groups.
* The word problem for certain formal languages.
* The problem of determining if a given set of Wang tiles can tile the plane.
* The problem of determining the Kolmogorov complexity of a string.
* Determination of the solvability of a Diophantine equation, known as Hilbert's tenth problem
* Determining whether two finite simplicial complexes are homeomorphic
* Determining whether the fundamental group of a finite simplicial complex is trivial
* Determining if a context-free grammar generates all possible strings, or if it is ambiguous.
* Given two context-free grammars, determining whether they generate the same set of strings, or whether one generates a subset of the strings generated by the other, or whether there is any string at all that both generate.
* Determining whether a given initial point with rational coordinates is periodic, or whether it lies in the basin of attraction of a given open set, in a piecewise-linear iterated map in two dimensions, or in a piecewise-linear flow in three dimensions.

Partial Bibliography

cite book | last = Brookshear | first = J. Glenn | title = Theory of Computation: Formal Languages, Automata, and Complexity | year = 1989 | publisher = Benjamin/Cummings Publishing Company, Inc. | location = Redwood City, California 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.

cite book | last = Moret | first = B. M. E. | co-author = H. D. Shapiro | title = Algorithms from P to NP, volume 1 - Design and Efficiency | year = 1991 | publisher = Benjamin/Cummings Publishing Company, Inc. | location = Redwood City, California Discusses intractability of problems with algorithms having exponential performance in Chapter 2, "Mathematical techniques for the analysis of algorithms."