Da pokažemo, da je jezik odločljiv, potrebujemo , da ustvarimo Turingov stroj, ki se bo ustavil na katerem koli vhodnem nizu iz abecede jezika. Ker je M dfa, že imamo Turingov stroj in samo moramo pokazati, da se dfa ustavi pri vsakem vnosu.
Kako izračunate odločljivost?
Jezik je odločljiv, če in samo če sta prepoznavna in njegova dopolnila. Dokaz. Če je jezik odločljiv, potem je njegov komplement odločljiv (z zaprtjem pod komplementacijo).
Kako dokažete Turingovo odločljivost?
Dokaži, da je jezik, ki ga prepozna, enak danemu jeziku in da se algoritem ustavi na vseh vhodih. Če želite dokazati, da je dani jezik Turingov prepoznaven: Sestavite algoritem, ki sprejema točno tiste nize, ki so v jezikuZavrniti mora ali zastaviti na kateri koli niz, ki ni v jeziku.
Kako veš, ali je jezik prepoznaven?
Jezik L je prepoznaven, če in samo če obstaja preveritelj za L, kjer je preveritelj Turingov stroj, ki se ustavi na vseh vhodih in za vse w∈Σ∗, w∈L↔∃c∈Σ∗. V sprejema ⟨w, c⟩.
Kako pokažete, da je težava nerešljiva?
Problem popolnosti je nerazločljiv
problem ustavljanja lahko uporabimo, da pokažemo, da so druge težave nerešljive. Problem popolnosti: Za funkcijo (ali program) F rečemo, da je totalna, če je F(x) definiran za vse x (ali podobno, če se F(x) ustavi za vse x). Določitev, ali je funkcija F skupna ali ne, je nemogoče določiti.
