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