Jednym z nich jest właśnie zdanie 17 Gen r.
Przykłady problemów nierozstrzygalnych Nierozstrzygalność problemu stopu
Nie istnieje maszyna Turinga rozstrzygająca w skończonej liczbie kroków, czy dowolna maszyna Turinga zakończy pracę.
Nierozstrzygalność Entscheidungsproblem
Nie istnieje algorytm rozstrzygający w skończonej liczbie kroków, czy dana formuła jest dowodliwa w wybranym systemie aksjomatycznym.
Nierozstrzygalność pytania o istnienie rozwiązania równania diofantycznego
Równanie diofantyczne jest równaniem postaci:
gdzie jest wielomianem o współczynnikach całkowitych. Współczynniki wielomianu D można jednoznacznie zakodować w postaci odpowiedniego, skończonego ciągu liczb całkowitych.
Nie istnieje maszyna Turinga rozstrzygająca w skończonej liczbie kroków, czy dane równanie diofantyczne ma rozwiązanie w dziedzinie liczb całkowitych.
Nierozstrzygalność problemu równoważności dla rachunku lambda Wyobraźmy sobie, że istnieje algorytm w postaci λ-wyrażenia rozstrzygający, czy dwa λ-wyrażenia są równoważne: algorytm bierze cztery wyrażenia, po czym zwraca trzecie, jeśli dwa pierwsze są równoważne lub czwarte w przeciwnym wypadku.
Jeśli zwróci true, wyrażenie zwróci false, jeśli zwróci false, wyrażenie zwróci true.