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

Nierozstrzygalność problemu stopu[edytuj | edytuj kod]

 Osobny artykuł: Problem stopu.

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

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.