Da bismo pokazali da se jezik može odlučiti, trebamo za stvaranje Turingovog stroja koji će se zaustaviti na bilo kojem ulaznom nizu iz abecede jezika. Budući da je M dfa, već imamo Turingov stroj i samo trebamo pokazati da se dfa zaustavlja na svakom unosu.
Kako izračunati Odlučivost?
Jezik je odlučiv ako i samo ako su on i njegova dopuna prepoznatljivi. Dokaz. Ako je jezik odlučiv, tada je njegov komplement odlučujući (zatvaranjem pod komplementacijom).
Kako dokazujete Turingovu odluku?
Dokažite da je jezik koji prepoznaje jednak zadanom jeziku i da se algoritam zaustavlja na svim ulazima. Da biste dokazali da je dati jezik prepoznatljiv po Turingu: Konstruirajte algoritam koji prihvaća točno one nizove koji su u jezikuMora ili odbiti ili zapeti na bilo kojem nizu koji nije na jeziku.
Kako znati je li jezik prepoznatljiv?
Jezik L je prepoznatljiv ako i samo ako postoji verifikator za L, gdje je verifikator Turingov stroj koji se zaustavlja na svim ulazima i za sve w∈Σ∗, w∈L↔∃c∈Σ∗. V prihvaća ⟨w, c⟩.
Kako pokazujete da je problem neodlučiv?
Problem totaliteta je neodlučiv
problem zaustavljanja može se koristiti da pokaže da su drugi problemi neodlučivi. Problem totaliteta: Kaže se da je funkcija (ili program) F totalna ako je F(x) definiran za sve x (ili slično, ako se F(x) zaustavi za sve x). Određivanje je li funkcija F ukupna ili nije neodlučivo je.