SML kordamisküsimustele vastused.
Turingi masinate numeratsioon.
Turingi mõttes mittearvutatavad funktsioonid. Eneselerakendatavuse ja
peatumise probleemi mittelahenduvus. Rice'i teoreem (tõestuseta).
Järeldused programmeerimise jaoks.
Def 5. Ütleme, et Turingi masin M lahendab omadust R, kui tema poolt arvutatav ühe muutuja
funktsioon on
1, ,
() =
0, .
Teoreem 3.Ei leidu Turingi masinat, mis lahendaks enese,erakendatavuse omadust.
Tõestus lk 124
Teoreem 4. Ei leidu Turingi masinat, mis kontrolliks argumentide x ja y järgi, kas masin Tx
lõpetab argumendil y töö lõpliku arvu sammudega.
Tõestus lk. 125
Teoreem 5. (Rice'i teoreem) Olgu A kõigi Turingi mõttes arvutatavate funktsioonide hulga
mittetühi pärisalamhulk. Ei leidu Turingi masinat, mis kontrolliks argumendi x järgi, kas Turingi
masina Tx poolt arvutatav funktsioon kuulub hulka A.
III. Predikaatarvutus
Predikaadid ja indiviidid. Kvantorid.
annaabi.ee 
