Introduction to Recursive Functions

College of Arts and Philosophy, Charles University, course syllabus

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