Z Wikipedii

Rozstrzygalność (decydowalność) problemu matematycznego to następująca jego właściwość: zawsze można określić czy dana odpowiedź na pytanie stawiane przez problem jest poprawna.

Na przykład pytanie czy w dziedzinie liczb rzeczywistych dwa wyrażenia złożone z liczb, zmiennych i plusów mają równą wartość jest rozstrzygalne: np. x + 2 + 3 i 5 + x są równoważne, natomiast 4 + x i 4 + y już nie.

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

Zasugerowano, aby artykuł Obliczalność zbioru twierdzeń zintegrować z tym artykułem lub sekcją.

Spis treści 1 Przykłady z dziedziny informatyki 1.1 Nierozstrzygalność problemu stopu 1.2 Nierozstrzygalność problemu równoważności dla rachunku lambda 1.3 Zobacz też

[edytuj] Przykłady z dziedziny informatyki

[edytuj] Nierozstrzygalność problemu stopu

Wyobraźmy sobie, że istnieje algorytm pobierający funkcję i argument, i rozstrzygający czy dany algorytm się zatrzyma dla danego argumentu. Zapytamy go więc czy zatrzyma się f dla argumentu g:

def f(g)
{
    if (zatrzyma_się(f,g))
        nieskończona_pętla()
    else
        return
}

Jeśli stwierdzimy, że się zatrzyma to się nie zatrzyma, jeśli natomiast stwierdzimy, że się nie zatrzyma, to się zatrzyma.

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

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

[edytuj] Zobacz też

• przegląd zagadnień z zakresu matematyki.