"formalisatsioonide" - 1 õppematerjal

SML kordamisküsimustele vastused.

Tõestus lk. 93 Lausearvutuse täielikkuse teoreemi põhilemma ja täilekkuse teoreem (tõestustega) Teoreem 4. Kui sekventsi 1 , 2 , ... , G valemkuju on samaselt tõene, siis sekvents on tuletatav. Tõestus lk. 96 II. Turingi masinad Turingi masin. Arvuliste funktsioonide arvutamine Turingi masinal. Kõike, mida saab arvutada protsessiga, mis vastab meie intuitsioonile algoritmilisest protsessist, saab arvutada ka Turingi masina abil. Teesi analooge saab kirja panna ka algoritmi teiste formalisatsioonide kohta. Churchi teesi ei saa tõestada, sest ta seob intuitiivse mitteformaalse mõiste täpse formaalse mõistega. Kuid teda saab ümber lükata. 5 Turingi masina töötamine: · Aeg on jagatud diskreetseteks ühikuteks, taktideks. · Igal taktil määratakse pea all oleva sümboli ja masina seisundi järgi järgmisena täidetava käsu vasak pool.