Loengu sisu  (järg konspektis)

Ülesanded ( 2/1 p.)

Testid

1.

12.II

Sissejuhatus. Algoritmi mõiste formaliseerimisest.

2.

13.II

 LRF definitsioon. Lihtsamad omadused. LRF näited. Lihtrekursiivsed hulgad (algus)

AT01

3.

19.II

Lihtrekursiivsed hulgad. Lihtrekursiivsed predikaadid – tõkestatud kvantoriteni.

1. Näidata, et [x/y] on LRF (kui määrata väärtused y=0 jaoks)

4.

20.II

 Lihtrekursiivsed predikaadid. Universaalne funktsioon, (Ackermanni funktsioon- iseseisvalt lugeda).

2. Tõkestatud suurima lahendi leidmise operaatori lihtrekursiivsus.

AT02

5.

26.II

ORF definitsioon. Täisrekursiivse programmeerimiskeele olemasolu probleem. Ülesanded lihtrekursiivsuse tõestamise kohta. ORF arvutatavus (baaslemma ).

6.

27.II

ORF arvutatavus (tõestuse lõpp). Arvutatavate funktsioonide rekursiivsus (situatsioonide numeratsioon, algseisundi number)

7.

5.III

 Arvutatavate f-nide rekursiivsus. ORF numeratsioon. Universaalne funktsioon. s-m-n-teoreem.

8.

6.III

Esimesed mittearvutatavuse teoreemid. Rekursiivsed ja rekursiivselt loetletavad hulgad (teor.7-9)

AT03* 

9.

12.III

Rekursiivsed ja rekursiivselt loetletavad hulgad (teor.10-13).
Ei lugenud: teor. 14, Rek. Permutatsioonid.
n-dimensionaalsed hulgad (teor 18).

10.

13.III

Projektsiooniteoreemid. Püsipunkti teoreem. Rice“i teoreem.

3. Uurida, kas naturaalarvu järgi temale vastava paari komponentide leidmise funktsioonid π on lihtrekursiivsed.

11.

19.III

  Ülesanded (hulkade/predikaatide omaduste säilimine operatsioonidel).

 4. Tuua näide, kus kolõpliku hulga originaal täisrekursiivse funktsiooniga kujutamisel pole lihtrekursiivne.

12.

20.III

  Ülesanded (hulkade/predikaatide omaduste säilimine operatsioonidel)

 5. Tuua näide, kus A on kolõplik (näiteks N), f on LRF ja f(A) pole rekursiivne.

AT05, AT06

13.

26.III

Ülesanded. Rice-Shapiro teoreem. Lahenduvad ja loetletavad programmide omadused.

 AT04

14.

27.III

Kordamine: predikaatloogika mudeliteooria. Interpretatsioonid. Struktuuri I järku teooria.

15.

2.IV

Samaselt tõesus, kehtestatavus, samaväärsus. Lõpliku kandjaga struktuurid. 

16.

3.IV

Bethi tabelid

17.

9.IV

1. Kontrolltöö (test klassis 003).
2. Bethi tabeli ülesanded arvutil. Kodune ülesanne: lahendada
kaustas M:\Loogika\ML&AT\Beth ülesannete kogud  lausearvutus1, pred-1, pred-2, pred3, lopmatud.

18.

10.IV

 Reaalarvude järjestuse elementaarteooria.Järeldumine.

19.

16.IV

Aksiomaatilised teooriad. Aks. teooriate algoritmiteoreetilised omadused (teor 1).

20.

17.IV

Aks. teooriate algoritmiteoreetilised omadused (lõpp). Lausearvutus. Predikaatarvutus. Võrdusega predikaatarvutus.

21.

23.IV

Praktikum (klass 003): Puhas predikaatarvutus.Võrdusega predikaatarvutus:  ülesannete kogu M:\Loogika\ML&AT\EQ\EQ.TSK (välja arvatud üles. 16). Tudengifail saata kirjaga 2 nädala jooksul.

Üles 16.

22.

24.IV

Võrdusega predikaatarvutus. Esimest järku aksiomaatilised teooriad. Rühmateooria aksioomid ja Peano aritmeetika aksioomid.

23.

30.IV

Teooria laiendamine, mudeli ahendamine.

24.

7.V

Praktikum (klass 003): Tuletamine aritmeetikas.
H:\public_html\ML&AT\Tulet-aritmeetikas.docx

25.

8.V

Kanooniline mudel. Laiendamine Henkini teooriaks. Laiendamine süntaktiliselt täielikuks.

26.

14.V

Praktikum (klass 003): Tuletamine aritmeetikas.

27.

15.V

Teoreem mudelist. Predikaatloogika täielikkus. PA mudelid. Formaalse aritmeetika mittetäielikkus. Aritmeetika mittevasturääkivuse probleem.

28.

21.V

Kontrolltöö (003): tuletamine (võrdusega pred.-arvutus ja formaalne aritmeetika).

29.

22.V

Genereerivad grammatikad. Loetletavate sõnahulkade esitamine grammatika abil.

 30.

28.V

 Sõnade ekvivalentsi probleem. Thue poolsüsteemid.

 31.

 29.V