List of undecidable problems
From Wikipedia, the free encyclopedia
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. Note that there are uncountably many undecidable problems, so this list is necessarily incomplete.
[edit] 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.
[edit] Other problems
- the Post correspondence problem
- the word problem for groups
- the word problem for certain formal languages
- the Wang tile
- Kolmogorov Complexity
- Penrose tiling
- Determination of the solvability of a Diophantine equation, known as Hilbert's tenth problem
- Determining whether two finite simplicial complexes are homeomorphic
- Determining whether the fundamental group of a finite simplicial complex is trivial
