Obliczalność — podsumowanie

Każdej maszynie Turinga M o alfabecie wejściowym 0,1 i alfabecie pomocniczym 0,1, B, możemy przypisać słowo ⟨M⟩ ∈ {0, 1}^{∗} zwane kodem maszyny M. Na odwrót, każde słowo w ∈ {0, 1}^{∗} jest kodem pewnej maszyny Turinga M_{w}.

Zbiór słów L_{u} = {wv : v ∈ L(M_{w})} nazywamy j_{}ezykiem uniwersalnym, gdyż zawiera on informacj_{}e o wszystkich j_{}ezykach akceptowanych przez maszyny Turinga. Istnieje maszyna Turinga akceptuj_{}aca ten właśnie j_{}ezyk, tzw. maszyna uniwersalna. Jest wi_{}ec on cz_{}eściowo obliczalny.

J_{}ezyk uniwersalny nie jest jednak całkowicie obliczalny.

A zatem, z dokładności_{}a do tezy Turinga–Churcha możemy stwierdzić :

Nie istnieje algorytm, który dla danych: maszyny Turinga M i słowa w, odpowiada na pytanie, czy w ∈ L(M).

Jednak istnieje algorytm, który odpowiada na wspomniane wyżej pytanie, o ile odpowiedź jest twierdz_{}aca, a w przeciwnym przypadku nie daje odpowiedzi (obliczenie może być nieskończone).

Nierozstrzygalność algorytmiczna tego problemu poci_{}aga za sob_{}a nierozstrzygalność wielu innych.

Twierdzenie Rice’a

Gdy A ⊆ P(N) jest dowoln_{}a rodzin_{}a zbiorów, tak_{}a, że istniej_{}a zbiory cz_{}eściowo obliczalne A ∈ A (przykład) i B ∉ A (kontrprzykład), to j_{}ezyk

{w : L(M_{w}) ∈ A}

nie jest obliczalny.

W szczególności, dla danej maszyny M nie jest rozstrzygalne, czy L(M) jest

• niepusty,

• jednoelementowy,

• skończony,

• regularny,

• równy zbiorowi wszystkich słów,

• równy L(M_{0}), dla ustalonej maszyny M_{0} etc.

Nierozstrzygalność

Ogólnie, problem obliczeniowy nazwiemy algorytmicznie nierozstrzygalnym, jeśli, przedstawiony jako j_{}ezyk, nie jest całkowicie obliczalny.

Oto przykłady problemów nierozstrzygalnych.

• Czy dane dwa programy w j_{}ezyku Pascal obliczaj_{}a t_{}e sam_{}a funkcj_{}e ?

• Problem Posta. Dane dwie listy słów : u_{1}, …, u_{n} ∈ Σ^{∗} i w_{1}, …, w_{n} ∈ Σ^{∗}. Czy istnieje ci_{}ag indeksów i_{1}, …, i_{m} ∈ {1, …, n}, taki, że u_{i_{1}} … u_{i_{n}} = w_{i_{1}} … w_{i_{n}} ?

• Dla danych gramatyk bezkontekstowych G_{1}, G_{2},

– czy L(G_{1}) = L(G_{2}) ?

– czy L(G_{1}) ∩ L(G_{2}) ≠ ∅ ?

– czy L(G_{1}) = Σ^{∗} ?

– czy G jest gramatyk_{}a jednoznaczn_{}a ?

• Dziesi _{}aty problem Hilberta. Czy dane równanie diofantyczne posiada rozwi_{}azanie w liczbach całkowitych? (równanie diofantyczne : równość dwóch wyrażeń arytmetycznych o współczynnikach całkowitych)