Näyttääksemme, että kieli on päätettävissä, meidän on luotava Turingin kone, joka pysähtyy missä tahansa syötemerkkijonossa kielen aakkosista. Koska M on dfa, meillä on jo Turingin kone ja meidän on vain osoitettava, että dfa pysähtyy jokaisella syötteellä.
Miten lasket päätettävyyden?
Kieli on pääteltävissä, jos ja vain jos se ja sen komplementti ovat tunnistettavissa. Todiste. Jos kieli on päätettävissä, niin sen komplementti on päätettävissä (sulkemalla täydennyksen alle).
Miten todistat Turingin päättävyyden?
Todista, että sen tunnistama kieli on sama kuin annettu kieli ja että algoritmi pysähtyy kaikissa tuloissa. Todistaaksesi, että tietty kieli on Turingin tunnistettavissa: Luo algoritmi, joka hyväksyy täsmälleen ne merkkijonot, jotka ovat kielelläSen on joko hylättävä tai silmoitettu mikä tahansa merkkijono, joka ei ole kyseisellä kielellä.
Mistä tiedät, onko kieli tunnistettavissa?
Kieli L on tunnistettavissa, jos ja vain jos on olemassa todentaja L, jossa todentaja on Turingin kone, joka pysähtyy kaikilla syötteillä ja kaikilla w∈Σ∗, w∈L↔∃c∈Σ∗. V hyväksyy ⟨w, c⟩.
Miten osoitat, että ongelma on ratkaisematon?
Totaalisuusongelma on ratkaisematon
Pysäytysongelma voidaan käyttää osoittamaan, että muut ongelmat ovat ratkaisemattomia. Totaliteettiongelma: Funktion (tai ohjelman) F sanotaan olevan kokonaisuus, jos F(x) on määritelty kaikille x:ille (tai vastaavasti, jos F(x) pysähtyy kaikille x:ille). On mahdotonta määrittää, onko funktio F kokonaismäärä.
