List of undecidable problems

Problems in [logic]

• Hilbert's Entscheidungsproblem.
• Type inference and type checking for the second-order lambda calculus.
• 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.

  Problems about [abstract machine]s

• The halting problem and the mortality problem.
• Determining whether a Turing machine is a busy beaver champion.
• 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 Minsky 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.

  Problems about matrices">Matrix (mathematics)">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.
• 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 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 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, known as the zero-equivalence problem
• "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.
• Determining the domain of a solution to an ordinary differential equation of the form

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 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.
• Determining whether a λ-calculus formula has a normal form.
• Conway's Game of Life 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 .
• Planning in a Partially observable Markov decision process.
• .