Rozstrzygalność

Rozstrzygalność (decydowalność) problemu matematycznego to następująca jego właściwość: istnieje algorytm, który oblicza odpowiedź na dowolne pytanie stawiane przez problem.

Problem może być nierozstrzygalny, jeśli jego rozstrzygalność prowadziłaby do powstania paradoksów.

Przykłady z dziedziny informatyki

Nierozstrzygalność problemu równoważności dla rachunku lambda

Wyobraźmy sobie, że istnieje algorytm w postaci λ-wyrażenia E 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.

$Y (\lambda f . E f\,\mathrm{true}\,\mathrm{false}\,\mathrm{true})$

Jeśli $E$ zwróci true, wyrażenie zwróci false, jeśli $E$ zwróci false, wyrażenie zwróci true.