Matemaatiline loogika ja algoritmiteooria
kevadsemestril 2012
Punktiülesanded
Ülesanded antakse loengutel. Iga ülesanne tuleb
lahendada nende tulemuste baasil, mis on ülesande andmise ajaks
loengus läbi võetud. Järgmiste loengute materjali
kasutada ei tohi.
Lahendused vormistada mingi programmi abil, mis
võimaldab konstrueerida antud ülesande jaoks vajalikke
valemeid.
Esimene õige lahendus annab 2 punkti, neli
järgmist 1 punkti.
|
Nr |
Ülesanne |
Antud |
Tähtaeg |
|
1. |
Defineerida lihtrekursiivse
funktsiooni mõiste täisarvude hulga jaoks. Sealjuures
kirjutada välja ka kõigi suuruste lubatud
muutumispiirid (näiteks n=1, 2, 3, ..., |
9.II |
23.II |
|
2. |
2. Tõestada, et jagatise täisosa leidmine [x/y] on lihtrekursiivne funktsioon (kui määrata väärtused y=0 jaoks). |
13.II |
27.II |
|
3. |
3. Tõestada, et tõkestatud suurima arvu operaatori rakendamine lihtrekursiivsele predikaadile annab lihtrekursiivse funktsiooni. |
16.II |
1.III |
|
4. |
4. Loengus näitasime, et teades, et TM Tx 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. |
8.III |
22.III |
|
5. |
|
|
|
|
6. |
|
|
|
|
7. |
|
|
|
|
8. |
|
|
|
|
9. |
|
|
|
|
10. |
|
|
|
|
|
|
|
|