List of undecidable problem - Definition and Overview

In computability theory, an undecidable problem is a problem whose language is not a recursively enumerable set. More informally, such problems cannot be solved by computers; see decidability. This is a list of undecidable problems.

Problems related to abstract machines

• the halting problem
• Rice's theorem states that all non-trivial properties of computer programs are undecidable.
• Determining if a context-free grammar generates all possible strings, or if it is ambiguous
• Determining if two context-free grammars generate some identical string, if they generate the same set of strings, or if one generates all the strings generated by the other

Other problems

• Gödel's first incompleteness theorem: there is a statement that cannot be proved or disproved in any axiomatic system strong enough to define the natural numbers
• Goodstein's theorem about natural numbers and Kruskal's tree theorem, on which Kruskal's algorithm is based, cannot be proven from Peano arithmetic
• the Post correspondence problem
• the word problem for groups
• the word problem for formal languages
• the Wang tile
• Penrose tiling

See also: list of statements undecidable in ZFC