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.

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

Other problems

• the Post correspondence problem
• the word problem for groups
• the word problem for certain formal languages
• the Wang tile
• Penrose tiling
• Determination of the solvability of a Diophantine equation, known as Hilbert's tenth problem
• Determing whether two finite simplicial complexes are homeomorphic
• Determining whether the fundamental group of a finite simplicial complex is trivial

Mathematics-related lists | Theory of computation | Recursion theory

Недоказуемые утверждения