Rozstrzygalność

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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[edytuj]

Nierozstrzygalność problemu stopu[edytuj]

 Osobny artykuł: Problem stopu.

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

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.

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