List of undecidable problems

In computability theory, an undecidable problem is a type of computational problem that requires a yes/no answer, but where there cannot possibly be any computer program that always gives the correct answer; that is any possible program would sometimes give the wrong answer or run forever without giving any answer. More formally, an undecidable problem is a problem whose language is not a recursive set; see decidability. There are uncountably many undecidable problems, so the list below is necessarily incomplete. Though undecidable languages are not recursive languages, they may be subsets of Turing recognizable languages i.e. such undecidable languages may be recursively enumerable.

Many, if not most, undecidable problems in mathematics can be posed as word problems: determining when two distinct strings of symbols (encoding some mathematical concept or object) represent the same object or not.

For undecidability in axiomatic mathematics, see list of statements undecidable in ZFC.

Problems in logic

• Hilbert's Entscheidungsproblem.
• Type inference and type checking for the second-order lambda calculus (or equivalent).^[1]
• Determining whether a first-order sentence in the logic of graphs can be realized by a finite undirected graph.^[2]

Problems about abstract machines

• The halting problem (determining whether a Turing machine halts on a given input) and the mortality problem (determining whether it halts for every starting configuration).
• Determining whether a Turing machine is a busy beaver champion (i.e., is the longest-running among halting Turing machines with the same number of states).
• Rice's theorem states that for all nontrivial properties of partial functions, it is undecidable whether a given machine computes a partial function with that property.

Problems about matrices

• The mortal matrix problem: determining, given a finite set of n × n matrices with integer entries, whether they can be multiplied in some order, possibly with repetition, to yield the zero matrix. This is known to be undecidable for a set of six or more 3 × 3 matrices, or a set of two 15 × 15 matrices.^[3]
• Determining whether a finite set of upper triangular 3 × 3 matrices with nonnegative integer entries generates a free semigroup.
• Determining whether two finitely generated subsemigroups of M_n(Z) have a common element.

Problems in combinatorial group theory

• The word problem for groups.
• The conjugacy problem.
• The group isomorphism problem.

Problems in topology

• Determining whether two finite simplicial complexes are homeomorphic.
• Determining whether a finite simplicial complex is (homeomorphic to) a manifold.
• Determining whether the fundamental group of a finite simplicial complex is trivial.

Problems in analysis

• For functions in certain classes, the problem of determining: whether two functions are equal; the zeroes of a function; whether the indefinite integral of a function is also in the class. For examples, see references in Stallworth and Roush, below. (These problems are not always undecidable. It depends on the class. For example, there is an effective decision procedure for the elementary integration of any function which belongs to a field of transcendental elementary functions, the Risch algorithm.) See Richardson's theorem.
• "The problem of deciding whether the definite contour multiple integral of an elementary meromorphic function is zero over an everywhere real analytic manifold on which it is analytic." Its decidability would contradict the solution to Hilbert's tenth problem.^[4]

Other problems

• The Post correspondence problem.
• The problem of determining if a given set of Wang tiles can tile the plane.
• The problem whether a Tag system halts.
• The problem of determining the Kolmogorov complexity of a string.
• Hilbert's tenth problem: the problem of deciding whether a Diophantine equation (multivariable polynomial equation) has a solution in integers.
• 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.^[5]
• Determining whether a λ-calculus formula has a normal form.
• Finding the lowest possible air fare between two cities under only the condition that the database of air fares, routing rules, flights and airports is finite.^[6]

See also

• List of unsolved problems
• Reduction (complexity)

Notes

1. Wells, J. B. (1993). "Typability and type checking in the second-order lambda-calculus are equivalent and undecidable". Tech. Rep. 93-011. Comput. Sci. Dept., Boston Univ. CiteSeerX 10.1.1.31.3590.
2. Trahtenbrot, B. A. (1950). "The impossibility of an algorithm for the decision problem for finite domains". Doklady Akad. Nauk SSSR (N.S.). 70: 569–572. MR 0033784.
3. Cassaigne, Julien; Halava, Vesa; Harju, Tero; Nicolas, Francois (2014). "Tighter Undecidability Bounds for Matrix Mortality, Zero-in-the-Corner Problems, and More". arXiv:1404.0644 [cs.DM].
4. Stallworth, Daniel T. and Fred W. Roush An Undecidable Property of Definite Integrals Proceedings of the American Mathematical Society Volume 125, Number 7, July 1997, Pages 2147-2148
5. Moore, Cristopher (1990), "Unpredictability and undecidability in dynamical systems" (PDF), Physical Review Letters, 64 (20): 2354–2357, doi:10.1103/PhysRevLett.64.2354, PMID 10041691.
6. http://www.itasoftware.com/pdf/ComplexityofArlineTravelPlanning_Carl_Sep-03.pdf

Bibliography

• 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.
• Halava, Vesa (1997). "Decidable and undecidable problems in matrix theory". TUCS technical report. 127. Turku Centre for Computer Science. CiteSeerX 10.1.1.31.5792.
• Moret, B. M. E.; H. D. Shapiro (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."
• Weinberger, Shmuel (2005). Computers, rigidity, and moduli. Princeton, NJ: Princeton University Press. Discusses undecidability of the word problem for groups, and of various problems in topology.

Further reading

• Poonen, Bjorn (2 April 2012), Undecidable problems: a sampler, arXiv:1204.0299

External links

• Discussion at MathOverflow