Lai parādītu, ka valoda ir izšķirama, mums ir nepieciešams izveidot Tjūringa mašīnu, kas apstāsies pie jebkuras ievades virknes no valodas alfabēta. Tā kā M ir dfa, mums jau ir Tjūringa mašīna, un tikai jāparāda, ka dfa apstājas pie katras ievades.
Kā aprēķināt izšķiramību?
Valoda ir izšķirama tad un tikai tad, ja tā un tās papildinājums ir atpazīstami. Pierādījums. Ja valoda ir izšķirama, tad tās papildinājums ir izšķirams (aizverot papildinājumu).
Kā jūs pierāda Tjūringa spēju?
Pierādiet, ka valoda, ko tā atpazīst, ir vienāda ar doto valodu un ka algoritms apstājas pie visām ievadēm. Lai pierādītu, ka dotā valoda ir Tjūringa atpazīstama: Izveidojiet algoritmu, kas pieņem tieši tās virknes, kas ir valodāTai ir vai nu jānoraida, vai jāiekļauj cilpa jebkurai virknei, kas nav attiecīgajā valodā.
Kā zināt, vai valoda ir atpazīstama?
Valoda L ir atpazīstama tad un tikai tad, ja pastāv verificētājs L, kur verificētājs ir Tjūringa mašīna, kas apstājas pie visām ieejām un visiem w∈Σ∗, w∈L↔∃c∈Σ∗. V pieņem ⟨w, c⟩.
Kā parādīt, ka problēma ir neatrisināma?
Visuma problēma ir neatrisināma
Apturēšanas problēma var izmantot, lai parādītu, ka citas problēmas ir neatrisināmas. Totalitātes problēma: Funkciju (vai programmu) F sauc par kopējo, ja F(x) ir definēts visiem x (vai līdzīgi, ja F(x) apstājas visiem x). Nav iespējams noteikt, vai funkcija F ir summāra.
