Aby sme ukázali, že jazyk je rozhodovateľný, potrebujeme vytvoriť Turingov stroj, ktorý sa zastaví na akomkoľvek vstupnom reťazci z abecedy jazyka. Keďže M je dfa, už máme Turingov stroj a musíme ukázať, že dfa sa zastaví pri každom vstupe.
Ako vypočítate rozhodovateľnosť?
Jazyk je rozhoditeľný vtedy a len vtedy, ak je rozpoznateľný a jeho doplnok. Dôkaz. Ak je jazyk rozhodnuteľný, potom je rozhodnuteľný aj jeho doplnok (uzatvorením pod doplnením).
Ako dokážete Turingovu rozhodnuteľnosť?
Dokážte, že jazyk, ktorý rozpozná, je rovnaký ako daný jazyk a že algoritmus sa zastaví na všetkých vstupoch. Aby ste dokázali, že daný jazyk je Turingovo rozpoznateľný: Vytvorte algoritmus, ktorý akceptuje presne tie reťazce, ktoré sú v jazykuMusí to buď odmietnuť alebo zacykliť na akomkoľvek reťazci, ktorý nie je v jazyku.
Ako zistíte, či je jazyk rozpoznateľný?
Jazyk L je rozpoznateľný vtedy a len vtedy, ak existuje overovateľ pre L, kde overovateľom je Turingov stroj, ktorý sa zastaví na všetkých vstupoch a pre všetky w∈Σ∗, w∈L↔∃c∈Σ∗. V prijíma ⟨w, c⟩.
Ako ukážete, že problém je nerozhodnuteľný?
Problém totality je nerozhodnuteľný
Problém h alting problem možno použiť na preukázanie, že ostatné problémy sú nerozhodnuteľné. Problém totality: Funkcia (alebo program) F sa považuje za totálnu, ak je F(x) definované pre všetky x (alebo podobne, ak sa F(x) zastaví pre všetky x). Nie je možné rozhodnúť, či funkcia F je alebo nie je celková.
