Introduction to Recursive Functions

College of Arts and Philosophy, Charles University, course syllabus

Pokračováni je na http://www1.cuni.cz/~svejdar/.

Program ve šk. roce 2012/13

Prosím všechny účastníky kursu, aby věnovali pozornost seznamu cvičení. Postupně jej budeme doplňovat a u zkoušky se určitě uplatní.

25. října 2012: Uzavřenost třídy všech rekurzívních funkcí na operaci primitivní rekurze. Rekurzívnost funkcí, jako je mocnina a faktoriál. Nekonečná množina čísel je OR, právě když je oborem hodnot rostoucí FOR jedné proměnné. Zobecněná primitivní rekurze (ordinální rekurze).
23. října 2012: Kódování konečných množin a posloupností metodou dvou pravítek. Operace primitivní rekurze.
18. října 2012: Věta o projekci: RS množiny jsou právě ty množiny, které jsou definičními obory částečně rekurzívních funkcí. Neprázdné rekurzívně spočetné množiny čísel jsou právě ty množiny, které jsou obory hodnot rekurzívních funkcí jedné proměnné.
16. října 2012: Částečně rekurzívní funkce jsou právě ty funkce, které mají RS graf. Skolemova věta: funkce s OR grafem jsou právě ty funkce, které lze odvodit jedním užitím minimalizace z totální funkce.
11. října 2012: Souvislost rekurzívnosti totální funkce a rekurzívnosti jejího grafu. Párovací funkce. Rekurzívně spočetné množiny a jejich uzavřenost na operace.
9. října 2012: Jednoduché operace s rekurzívními funkcemi a podmínkami. Uzavřenost OR podmínek na booleovské operace a omezenou kvantifikaci.
4. října 2012: Δ₀ podmínky (omezené podmínky). Příklady: relace dělitelnosti, množina všech prvočísel, množina všech mocnin dvojky, grafy funkcí Mod a Div. Operace minimalizace.
2. října 2012: Úvod: šest základních funkcí a operace skládání.

Program ve šk. roce 2011/12

4. října 2011: Úvod: úloha jako zvláštní příklad množiny, množina (přirozených čísel nebo k-tic přirozených čísel) jako zvláštní případ funkce, přirozená čísla jako kódy syntaktických objektů.
D. cv.: Varianta A: cvičení 1(b) nebo cvičení 2 v dílu I. Varianta D: cvičení 1 celé plus cvičení 2.
6. října 2011: Operace primitivní rekurze a operace substituce (skládání funkcí). Definice primitivně rekurzívních funkcí, jednoduché příklady.
D. cv.: Varianta A: jedno z cvičení 3, 4(a) a 6. Varianta D: všechna tato cvičení.
11. října 2011: Příklady primitivně rekurzívních funkcí: násobení, umocňování, faktoriál, podmíněné odčítání. Jednoduché odvozené primitivně rekurzívní operace s funkcemi: přidání jalové proměnné, dosazení konstanty ... Operace minimalizace.
D. cv.: Tentokrát nezadáno.
13. října 2011: Definice primitivně, obecně a částečně rekurzívních funkcí, a (primitivně) rekurzívních a rekurzívně spočetných množin. Uzavřenost tříd PR a OR na booleovské operace.
D. cv.: Varianta A: cvičení 5 nebo cvičení 9. Varianta D: obě cvičení 5 a 9.
18. října 2011: Souvislost (primitivní) rekurzívnosti funkce s (primitivní) rekurzívností jejího grafu. Odvození funkce větvením, omezené kvantifikátory.
D. cv.: Cvičení 13(b) v dílu I, nebo některé z cvičení 2 nebo 4(a) v dílu II. Nebo všechna tato cvičení.
20. října 2011: Omezené kvantifikátory. Odvození funkce větvením, příklady.
D. cv.: Některé z cvičení 8, 10, 12, 14 v dílu I. Nebo všechna tato cvičení.
25. října 2011: Omezená minimalizace. Rostoucí posloupnost všech prvočísel. Kódování konečných posloupností.
D. cv.: cvičení 13(b) v dílu I nebo cvičení 5 v dílu II. Nebo obě tato cvičení.
27. října 2011: Kódování konečných posloupností. Zobecněná primitivní rekurze (ordinální rekurze).
D. Cv.: tentokrát oficiálně nezadáno, avšak relevantní je cvičení 15.
1. listopadu 2011: K cvičení 15 je podrobnější návod v knize na str. 112. Vývojové diagramy.
D. Cv.: Cvičení 16 nebo 17 (nebo obě) v dílu I.
3. listopadu 2011: Jednoduchý vyšší programovací jazyk, převzatý z Odifreddiho knihy a pojmenovaný SAL. Vztahy mezi všemi třemi výpočtovými modely (úvod).
D. Cv.: oficiálně nezadáno, avšak relevantní je cvičení 19.
8. listopadu 2011: Primitivní rekurzívnost všech funkcí počitatelných programem neobsahujícím while.
10. listopadu 2011: Ackermannova funkce.
D. Cv.: Cvičení 21(a).
15. listopadu 2011: Částečná rekurzívnost všech funkcí počitatelných vývojovými diagramy, dokončení. Věta o normální formě, věta o projekci.
D. Cv.: nezadáno.
22. listopadu 2011: Věta o projekci a její důsledky. Souvislost rekurzívnosti (primitivní rekurzívnosti, částečné rekurzívnosti) funkce a rekurzívnosti (primitivní rekurzívnosti, rekurzívní spočetnosti) jejího grafu. Postova věta.
D. Cv.: Některé z cvičení 3, 4(b), 6 (nebo všechna) v dílu II.
24. listopadu 2011: Charakterizace RS množiny čísel jako oboru hodnot (prosté) rekurzívní funkce. Věta o normální formě, schéma důkazu.
D. Cv.: Některé z cvičení 11, 13 (nebo obě) v dílu II.
29. listopadu 2011: Párovací funkce. Vlastnosti množin K a K₀, diagonalizace.
D. Cv.: nezadáno. O domácích cvičeních ve zbytku kursu domluveno, že nebudou vyžadována k určitému datu.
1. prosince 2011: Částečně rekurzívní funkce, která nemá žádné rekurzívní prodloužení. Rekurzívně neoddělitelné množiny. Aritmetická hierarchie. Množina Tot.
6. prosince 2011: Aritmetická hierarchie: uzavřenost tříd Σ_n a Π_n na operace. Stanovení aritmetické klasifikace množin Unb a Rec postupem zvaným Tarského-Kuratowského algoritmus.
D. Cv.: Stanovte aritmetickou klasifikaci množiny všech indexů všech neprázných RS množin, nebo všech x takových, že W_x je podmnožinou množiny -K.
13. prosince 2011: Σ_n-univerzální relace. Jejich užití k důkazu tvrzení, že aritmetická hierarchie nekolabuje.
Cvičení: cvičení 26 se vztahuje spíš k Postově větě a neoddělitelným množinám než k aritmetické hierarchii, avšak je celkem snadno řešitelné.
15. prosince 2011: Převeditelnost a kompletnost. Σ₁-kompletnost množiny K₀. Existence kompletních množin v každé z tříd Σ_n a Π_n.
Relevantní cvičení: Zdůvodněte podrobně, že Σ_n-kompletní množina není v Π_n (a také, že žádná z tříd Σ_n a Π_n není podtřídou druhé).
20. prosince 2011: Věta o parametrech, Σ₁-kompletnost množiny K.
Relevantní cvičení: 15.
22. prosince 2011: Užití věty o parametrech v úvahách o převeditelnosti. Π₂-kompletnost množin Unb a Tot.
Relevantní cvičení: 16-19 (18 a 19 jsou celkem obtížná, ale pro celý kurs dost podstatná).
3. ledna 2012: Věta o rekurzi. Indexové množiny a Riceova věta.
Relevantní cvičení: 23.
5. ledna 2012: Shrnutí a opakování indexových množin, věty o parametrech, aritmetické hierarchie a převeditelnosti. Užití věty o rekurzi k důkazu, že množina K není indexová.
Na Út 10.1. v 9:30 domluvena hromadná konzultace ke cvičením.

Summary

This course roughly follows chapters 1-7 and partly chapter 11 of the book [Rogers]. The introductory part is much more detailed than in [Rogers] and makes use mainly of [Odi].

Upřesnění sylabu a podmínek ke zkoušce

Ze sylabu nedošlo na produktivní, kreativní, imunní a prosté množiny, a nedošlo na cvičení 24 a 27.

Zkouška se bude skládat z písemné a následné ústní části. Písemná část odpadá u řešitelů domácích cvičení s podmínkou, že zkoušku složí v nejbližším zkouškovém období. Řešitel domácích cvičení je ten, kdo odevzdá všechna domácí cvičení (varianta A) v termínu, čili nejpozději v den následující přednášky. Varianta D (doháněcí) je zamýšlena pro ty, kteří se řešiteli teprve stát chtějí.

Ústní část zkoušky začíná vyřešením namátkově zvoleného příkladu nebo příkladů z obou dílů cvičení. K tomu si prosím připravte seznam cvičení, které umíte řešit, a to tak, aby obsahoval alespoň 16 cvičení z dílu I a alespoň 20 cvičení z dílu II. Schopnost vyřešit namátkově zvolené příklady z vlastního seznamu (po krátkém nakouknutí do své přípravy) je podmínkou sine qua non.

Recursive Functions and Sets

(Tento sylabus je v dílu II uveden česky.) Recursive functions (primitive, general, partial) and (primitive) recursive sets and relations. Definitions of these are accepted as a mathematical basis that captures the informal notion of algorithm. Derived operations on functions and predicates: Boolean operations, bounded quantifiers, bounded minimisation, definitions of a function by cases, inverse image of a set. ([DKK]: 96-111) Coding of finite sequences of natural numbers. Generalisation of the operation of primitive recursion (ordinal recursion). ([DKK]: 112-126)

Further Computational Models

Further computational models: Turing machines, ([DKK]: 1-34 or 1-40), flowchart diagrams ([Odi]: 61-74), a higher level programming language ([Odi]: ...). Mutual simulability of these models ([Odi]: 90-100), Church's thesis.

Main Results

Arithmetization of computations ([Odi]: 87), the Normal Form Theorem (Odi]: 90), enumeration of partial recursive functions and RE sets.
The diagonal method ([Odi]: 145-147). Recursive functions and sets that are not primitive recursive ([Odi]: 96). Recursively enumerable non-recursive sets. The halting problem ([Rogers]: 25 and 62-63). Universal partial recursive function.
The Projection Theorem. Connections between recursiveness of a function and recursiveness of its graph. Equivalent definitions of the notion of RE sets. Post's theorem. Closure of the class of primitive, general and RE sets under operations. ([Odi]: 135-147, [Rogers]: 57-69).
The Parameter Theorem ([Odi]: 131, [Rogers]: 57-69, called the s-n-m theorem there). m-reducibility, m-completeness. m-completeness of the halting problem. Productive and creative sets. Creativity of m-complete sets.
The Recursion Theorem ([Rogers]: 180, [DKK]: 216-219 and part II: 33-43). Rice's theorem. m-completeness of creative sets ([Rogers]: 183).
Imunne sets. Simple sets as an example of sets that are not m-complete. ([DKK]: -204, [Rogers]: 105-108).
Arithmetical hierarchy (part II of [DKK]: 188-189).

References

H Rogers, Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967
P Odifreddi, Classical Recursion Theory, North-Holland, Amsterdam, 1989
V Svejdar, Logika: neuplnost, slozitost a nutnost, Academia, Praha 2002
O Demuth, R Kryl, A Kucera, Teorie algoritmu, lecture notes, MFF UK, 1989

Download:

cvalg1.pdf, cvalg2.pdf, exercises.

My home page

Dept. of Logic

Charles University

Updated: by Vitezslav Svejdar