Norėdami parodyti, kad kalba yra sprendžiama, turime sukurti Tiuringo mašiną, kuri sustos bet kurioje įvesties eilutėje iš kalbos abėcėlės. Kadangi M yra dfa, mes jau turime Tiuringo mašiną ir tereikia parodyti, kad dfa sustoja kiekvienoje įvestyje.
Kaip apskaičiuojate sprendžiamumą?
Kalba yra sprendžiama tada ir tik tada, kai ji ir jos papildinys yra atpažįstami. Įrodymas. Jei kalba yra sprendžiama, tada jos papildymas yra sprendžiamas (užbaigus papildymą).
Kaip įrodyti Turingo ryžtingumą?
Įrodykite, kad kalba, kurią ji atpažįsta, yra lygi nurodytai kalbai ir kad algoritmas sustoja naudojant visas įvestis. Norėdami įrodyti, kad tam tikra kalba yra atpažįstama Turingo: Sukurkite algoritmą, kuris priimtų būtent tas eilutes, kurios yra kalbaJi turi arba atmesti, arba sudaryti ciklą bet kurioje eilutėje, kuri nėra ta kalba.
Kaip žinoti, ar kalba atpažįstama?
Kalba L yra atpažįstama tada ir tik tada, jei yra L tikrintojas, kur tikrintuvas yra Tiuringo mašina, sustabdanti visus įėjimus ir visus w∈Σ∗, w∈L↔∃c∈Σ∗. V priima ⟨w, c⟩.
Kaip parodyti, kad problema neišsprendžiama?
Visumos problema yra neišsprendžiama
stabdymo problema gali būti panaudota norint parodyti, kad kitos problemos yra neišsprendžiamos. Visumo problema: Funkcija (arba programa) F laikoma visumine, jei F(x) yra apibrėžta visiems x (arba panašiai, jei F(x) sustoja visiems x). Neįmanoma nustatyti, ar funkcija F yra visa, ar ne.
