List of undecidable problems

From Wikipedia, the free encyclopedia

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.

Contents 1 Problems related to logic 2 Problems related to abstract machines 3 Other problems 4 Partial Bibliography

[edit] Problems related to logic

• Type inference and type checking for the second-order lambda calculus (or equivalent).^[1]

[edit] 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.

[edit] 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.

[edit] Partial Bibliography

1. ^ J. B. Wells. "Typability and type checking in the second-order lambda-calculus are equivalent and undecidable." Tech. Rep. 93-011, Comput. Sci. Dept., Boston Univ., 1993.

Brookshear, J. Glenn (1989). Theory of Computation: Formal Languages, Automata, and Complexity. Redwood City, California: Benjamin/Cummings Publishing Company, Inc..  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.

Moret, B. M. E. (1991). Algorithms from P to NP, volume 1 - Design and Efficiency. Redwood City, California: Benjamin/Cummings Publishing Company, Inc..  Discusses intractability of problems with algorithms having exponential performance in Chapter 2, "Mathematical techniques for the analysis of algorithms."