Rice’o teorema apie kalbų savybes
Kiekvienai netrivialiai kalbos savybei klausimas, ar Tiuringo mašinos atpažįstama kalba ją turi, yra algoritmiškai neišsprendžiamas pagal mašinos aprašą.
Esminės žinios
Kiekvienai netrivialiai kalbos savybei klausimas, ar Tiuringo mašinos atpažįstama kalba ją turi, yra algoritmiškai neišsprendžiamas pagal mašinos aprašą. Netriviali reiškia, kad bent viena atpažįstama kalba šią savybę turi, o kita jos neturi; mašinos sintaksės savybėms ši teorema netaikoma.
Sąlygos ir taikymo ribos
- Savybė turi priklausyti tik nuo atpažįstamos kalbos.
- Algoritminis neišsprendžiamumas savaime nereiškia neatpažįstamumo.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
9 paskaitos Rice’o teoremos formuluotė, 31–32 skaidrės, ir taikymo kontrpavyzdžiai, 38–45 skaidrės.
2026-10-10 · Nepriklausoma DI redakcinė peržiūra: perskaitytas visas 241 glaustai suformuluoto teiginio rinkinys, įskaitant prielaidas, pateiktas lygtis bei susitarimus; taip pat perskaitytos visos 596 kilmės semantinės sąsajos; peržiūrėta visa 241 įrašo autoriaus tikslių šaltinių patikros matrica ir nurodyti apribojimai. Siekiant apžvelgti visą turimą medžiagą, perskaityti ankstesni 105 perimti Matematikos ir Informacijos įrašai. Toliau išvardyti tikslingai nepriklausomai patikrinti pirminių šaltinių skyriai; tai NEREIŠKIA, kad kiekvienas cituojamas šaltinio tekstas ar kiekvienas įrodymas buvo nepriklausomai perskaitytas iš naujo. Tai DI atliekama žinyno turinio peržiūra, o ne žmogaus suteiktas dalykinis patvirtinimas, išsamus vadovėlio atkūrimas ar eksperimentų pakartojimas. Patvirtinimo įrašas: mathematics-information-independent-content-review.1.
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- info-rice-theorem
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra