Jezik se imenuje odločljiv ali rekurziven, če obstaja Turingov stroj, ki sprejme in ustavi vsak vhodni niz w. Vsak odločljiv jezik je Turing-sprejemljiv. Odločitveni problem P je odločljiv, če je jezik L vseh primerov da v P odločljiv.
Kaj misliš z odločljivostjo?
: možnost odločanja posebej: zmožnost odločanja, kot sledi ali ne sledi iz aksiomov logičnega sistema Ali je bila logika popolna … ? In ali je bila odločljiva v smislu, da je obstajala metoda, ki je pokazala resničnost ali napačnost vsake izjave? -
Kakšna je razlika med odločljivostjo in nerazločljivostjo?
A odločitvena težava je odločljiva, če zanjo obstaja odločevalni algoritem. Sicer je neodločljivo. Da pokažemo, da je problem odločanja rešljiv, zadostuje, da podamo algoritem zanj.
Kako izračunate odločljivost?
Jezik je odločljiv, če in samo če sta prepoznavna in njegova dopolnila. Dokaz. Če je jezik odločljiv, potem je njegov komplement odločljiv (z zaprtjem pod komplementacijo).
Kaj je problem odločljivosti?
(definicija) Definicija: Odločevalni problem, ki ga je mogoče rešiti z algoritmom, ki se ustavi na vseh vhodih v končnem številu korakov Povezani jezik se imenuje odločljiv jezik. Znan tudi kot popolnoma odločljiv problem, algoritemsko rešljiv, rekurzivno rešljiv.
