Rekurzívne funkcie Flashcards
Definuj základné axiomatické funkcie
str. 95
Definuj skladanie funkcií
str. 95
definuj primitívnu rekurziu
str. 95
Opíš operáciu primitívnej rekurzie na sčítaní
str. 96, 10.1 príklad
definuj primitívne rekurzívnu funkciu
str. 96
Dokáž, že konštantná funkcia K0(x)=0 je primitívne rekurzívna
str. 96
Dokáž, že konšt. funkcia Kj(x)=j je primitívne rekurzívna
str. 96
Aké sú napríklad primitívne rekurzívne funkcie?
str. 96, veta 10.4
Dokáž, že x+y je primitiívne rekurzívna
str. 96
Dokáž, že x*y je primitiívne rekurzívna
str. 96
Dokáž, že y^x je primitiívne rekurzívna
str. 96
Dokáž, že sg(x) je primitiívne rekurzívna
str. 96
Dokáž, že not sg(x) je primitiívne rekurzívna
str. 96
Dokáž, že y-x je primitiívne rekurzívna
str. 96
Dokáž, že |x-y| je primitiívne rekurzívna
str. 96
Dokáž, že |x-y| je primitiívne rekurzívna
str. 96
Dokáž vetu 10.6
str. 97
Definuj minimalizáciu, regulárnu minimalizáciu
str. 98
Definuj rekurzívnu funkciu
str. 99
Definuj čiastnočne rekurzívnu funkciu
Čiastočná funkcia f je čiastočne rekurzívna ak f vznikne z funkcií 0, s a Inm konečným počtom operácií skladania, primitívnej rekurzie a minimalizácie
Dokáž vetu 10.7
str. 99
Dokáž pre F8 až F15, že sú primitívne rekurzívne
str. 99
Ako to je s existenciou TS pre funkcie? Čo z toho vyplýva?
str. 101
Vyslov a dokáž lemu o čiastočnej rekurzii pre funkciu pre kt. existuje TS
str. 101
Dokáž: Každú čiastočne rekurzívnu funkciu možno zostrojiť pomocou najviac jednej minimalizácie
str. 103
Dokáž: Každá totálna, čiastočne rekurzívna funkcia je rekurzívna
str. 104
Aká je to totálna funkcia?
Definovaná pre každý vstup z domény
Aká je to čiastočná funkcia?
Funkcia f z X do Y, ktorej def. obor je vlastná podmnožina X
Vyslov hlavnú vetu o ekvivalencii výpoćtových modelov
str. 104
Vyslov a dokáž hlavnú vetu o rekurzívnych funkciách
str. 104
Vyslov Churchovu tézu
na konci
