List of undecidable problems

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 and symbols).
• 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.
• The halting problem for a register machine: a finite-state automaton with no inputs and two counters that can be incremented, decremented, and tested for zero.
• Universality of a nondeterministic pushdown automaton: determining whether all words are accepted.
• Conway's Game of Life on whether, given an initial pattern and another pattern, the latter pattern can ever appear from the initial one.
• Rule 110 - most questions involving "can property X appear later" are undecidable.

Problems in formal logic and grammars

• Hilbert's Entscheidungsproblem.

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

• Determining whether a first-order sentence in the logic of graphs can be realized by a finite undirected graph.

• Trakhtenbrot's theorem - Finite satisfiability is undecidable.

• Satisfiability of first order Horn clauses.

• Determining whether a λ-calculus formula has a normal form.

• The Post correspondence problem: whether a tag system halts. There are many variants thereof.

• 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.

• Some other problems about CFG are also undecidable. See the page section for details.

• The emptiness problem: determining whether a language is empty given some representation of it, such as a finite-state automaton. It is undecidable for context-sensitive grammars.

Problems about matrices

• The mortal matrix problem.
• 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 integer matrices have a common element.
• Given a finite set of n×n matrices A_1, \dots, A_m, their joint spectral radius is defined as \limsup_{N \to \infty} \max_{i_1, \dots, i_N \in 1:m}|A_{i_1}\cdots, A_{i_N}|^{1/N}. For a set of 2 matrices with rational entries, the problem of deciding whether their joint spectral radius is \leq 1 is undecidable.

Problems in combinatorial group theory

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

Problems in topology

Main article: Simplicial complex recognition problem

• 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.
• Determining whether two non-simply connected 5-manifolds are homeomorphic, or if a 5-manifold is homeomorphic to S5.

Problems in number theory

• Hilbert's tenth problem: the problem of deciding whether a Diophantine equation (multivariable polynomial equation) has a solution in integers.

Problems in analysis

• For functions in certain classes, the problem of determining: whether two functions are equal, known as the zero-equivalence problem (see Richardson's theorem); the zeroes of a function; whether the indefinite integral of a function is also in the class. Of course, some subclasses of these problems are decidable. 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.
• "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", a consequence of the MRDP theorem resolving Hilbert's tenth problem.{{cite journal
• Determining the domain of a solution to an ordinary differential equation of the form ::\frac{dx}{dt} = p(t, x),~x(t_0)=x_0, :where x is a vector in Rn, p(t, x) is a vector of polynomials in t and x, and (t0, x0) belongs to Rn+1.

Problems in physics

• Determining whether a quantum mechanical system has a spectral gap.
• In the ray tracing problem for a 3-dimensional system of reflective or refractive objects, determining if a ray beginning at a given position and direction eventually reaches a certain point.
• Determining if a particle path of an ideal fluid on a three dimensional domain eventually reaches a certain region in space.

Other problems

• The problem of determining if a given set of Wang tiles can tile the plane.
• The problem of determining if a given set of polyominoes can tile the plane.
• The problem of determining the Kolmogorov complexity of a string.
• 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.
• Finding the capacity of an information-stable finite state machine channel.
• In network coding, determining whether a network is solvable.
• Determining whether a player has a winning strategy in a game of Magic: The Gathering.
• Planning in a partially observable Markov decision process.
• Planning air travel from one destination to another, when fares are taken into account.

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.

References

1. Wells, J. B.. (1993). "Typability and type checking in the second-order lambda-calculus are equivalent and undecidable". Comput. Sci. Dept., Boston Univ..
2. Trahtenbrot, B. A.. (1950). "The impossibility of an algorithm for the decision problem for finite domains". Doklady Akademii Nauk SSSR.
3. (June 1999). "On the undecidability of freeness of matrix semigroups". International Journal of Algebra and Computation.
4. (September 2007). "On Markov's Undecidability Theorem for Integer Matrices". Semigroup Forum.
5. (2000-10-09). "The boundedness of all products of a pair of matrices is undecidable". Systems & Control Letters.
6. Stillwell, John. (1993). "Classical Topology and Combinatorial Group Theory". Springer.
7. Keith O. Geddes, Stephen R. Czapor, George Labahn, ''Algorithms for Computer Algebra'', {{isbn. 0585332479, 2007, p. 81ff
8. (21 March 2008). "Boundedness of the Domain of Definition is Undecidable for Polynomial ODEs". Electronic Notes in Theoretical Computer Science.
9. (2015). "Undecidability of the spectral gap". Nature.
10. (17 August 2020). "Undecidability of the Spectral Gap in One Dimension". [[Physical Review X]].
11. "Computability and Complexity of Ray Tracing".
12. (2021). "Constructing Turing complete Euler flows in dimension 3". Proceedings of the National Academy of Sciences.
13. (2023). "Computability and Beltrami fields in Euclidean space". Journal de Mathématiques Pures et Appliquées.
14. Golomb, Solomon W.. (1970). "Tiling with Sets of Polyominoes". Journal of Combinatorial Theory.
15. Moore, Cristopher. (1990). "Unpredictability and undecidability in dynamical systems". [[Physical Review Letters]].
16. (2018). "Memory effects can make the transmission capability of a communication channel uncomputable". Nature Communications.
17. (2023). "Undecidability of Network Coding, Conditional Information Inequalities, and Conditional Independence Implication". IEEE Transactions on Information Theory.
18. (2022). "Representability of Matroids by c-Arrangements is Undecidable". [[Israel Journal of Mathematics]].
19. (2019-03-24). "Magic: The Gathering is Turing Complete".
20. "Computational Complexity of Air Travel Planning". [[ITA Software]].