Loengu sisu  (järg konspektis)

Ülesanded ( 2/1 p.)

Testid

1.

6.II

Sissejuhatus. Algoritmi mõiste formaliseerimisest.

2.

9.II

 LRF definitsioon. Lihtsamad omadused. LRF näited.

1. Anda täisarvude hulga Z jaoks sobiv lihtrekursiivse funktsiooni definitsioon.

AT01

3.

13.II

Lihtrekursiivsed hulgad. Lihtrekursiivsed predikaadid - algus.

2. Tõestada, et jagatise täisosa leidmine [x/y] on lihtrekursiivne funktsioon (kui määrata väärtused y=0 jaoks).

4.

16.II

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

3. Tõestada, et tõkestatud suurima arvu operaatori rakendamine lihtrekursiivsele predikaadile annab lihtrekursiivse funktsiooni.

AT02

5.

27.II

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

6.

1.III

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

7.

5.III

 Arvutatavate f-nide rekursiivsus. ORF numeratsioon. Universaalne funktsioon.

8.

8.III

s-m-n-teoreem. Esimesed mittearvutatavuse teoreemid. Rekursiivsed ja rekursiivselt loetletavad hulgad (teor.7-8)

4. Loengus näitasime, et teades, et TM T_x peatub sisendil y, saab välja uurida, kas arvutus on resultatiivne. Uurida, kas kehtib ka vastupidine seos peatumise ja resultatiivsuse vahel: mitteresultatiivsuse korral saab välja uurida, kas masin peatub.

9.

12.III

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

10.

15.III

Projektsiooniteoreemid. Püsipunkti teoreem.

11.

19.III

  Rice'i teoreem. (Lavrov-Ülesanded Maksimova)

12.

22.III

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

13.

26.III

Ülesanded (hulkade/predikaatide omaduste säilimine operatsioonidel). Rice-Shapiro teoreem. Lahenduvad ja loetletavad programmide omadused.

14.

29.IV

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

AT04, AT05, AT06

15.

2.IV

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

16.

5.IV

Bethi tabelid

17.

9.IV

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

18.

12.IV

Reaalarvude järjestuse elementaarteooria. 

Näidata, et reaalarvude järjestuse elementaarteooria lahenduvuse tõestuses saab etappi 3f4 põhjendada valemite 1-5 abil.

Näidata sama etapi 3f5 kohta

19.

16.IV

Järeldumine.Aksiomaatilised teooriad. Aks. teooriate algoritmiteoreetilised omadused (teor 1).

20.

19.IV

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

21.

23.IV

Praktikum (klass 203): 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.

22.

26.IV

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

23.

30.IV

Õppetööd ei toimu.

24.

3.V

Peano aritmeetika. Aritmeetiline ja Kleene-Mostowski hierarhia.

25.

7.V

Praktikum (klass 203): Tuletamine aritmeetikas.

26

10.V

Teooria laiendamine, mudeli ahendamine. Kanooniline mudel. Laiendamine Henkini teooriaks.

27

14.V

Praktikum (klass 203): Tuletamine aritmeetikas.

28.

17.V

Laiendamine süntaktiliselt täielikuks. Teoreem mudelist. Predikaatloogika täielikkus. Formaalse aritmeetika mittetäielikkus. Aritmeetika mittevasturääkivuse probleem.

29.

21.V

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

30.

24.V

Genereerivad grammatikad. Loetletavate sõnahulkade esitamine grammatika abilSõnade ekvivalentsi probleem. Thue poolsüsteemid.

 31.