Valodu sauc par izšķiramu vai rekursīvu, ja ir Tjūringa mašīna, kas pieņem un apstājas katrā ievades virknē w. Katra apspriežamā valoda ir Tjūringa pieņemama. Lēmuma problēma P ir izšķirama, ja ir izšķirama valoda L no visiem jā gadījumiem P.
Ko jūs domājat ar izšķiramību?
: var tikt īpaši izlemts: var tikt izlemts, vai tas izriet no loģiskās sistēmas aksiomām. Vai loģika bija pilnīga…? Un vai tas bija izšķirams tādā nozīmē, ka pastāvēja metode, kas demonstrēja katra apgalvojuma patiesumu vai nepatiesību? -
Kāda ir atšķirība starp izšķiramību un neizšķiramību?
A lēmuma problēma ir izšķirama, ja tai pastāv lēmuma pieņemšanas algoritms. Citādi tas ir neizšķirams. Lai parādītu, ka lēmuma problēma ir izlemjama, pietiek ar tās algoritmu.
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).
Kas ir izšķiramības problēma?
(definīcija) Definīcija: Lēmuma problēma, ko var atrisināt ar algoritmu, kas aptur visas ievades noteiktā soļu skaitā Saistīto valodu sauc par izšķiramu valodu. Zināms arī kā pilnībā izšķirama problēma, algoritmiski atrisināma, rekursīvi atrisināma.
