Študijné materiály pre kurz 1-INF-450 Logika pre informatikov ZS 2014/15

Recursive Functions

• Preliminaries

• Primitive Recursive Functions

• Primitive Recursive Functions
• Explicit Definitions
• Primitive Recursive Definitions
• Primitive Recursive Predicates and Bounded Minimalization
• Backward Recursion (README)
• Pairing Function and Arithmetization
• Course of Values Recursion(README)
• Recursion with Parameter Substitution (README)
• Nested Simple Recursion (README)
• Recursion with Measure(README)
• Regular Recursion(README)

• General Recursive Functions

• Beyond Primitive Recursion

• Ackermann Function (README)
• Universal Function for Primitive Recursive Functions (README)
• General Recursive Functions (README)
• μ-Recursive Functions (README)

• Partial Recursive Functions

• First recursion theorem (fixed point theorem) (README)
• Partial Recursive Functions (README)
• Normal Form Theorem (README)
• Partial μ-Recursive Functions (README)
• Recursively Decidable, Semidecidable and Undecidable Problems (README)