Študijné materiály pre kurz 2-INF-121 Teória vypočítateľnosti ZS 2008/09

Computability

• Preliminaries

• Primitive Recursive Functions

• Basic Development
• Bounded Minimalization
• Pairing Function
• Course of Values Recursion

• Beyond Primitive Recursion

• Ackermann-Peter Function (README)
• Universal Function for Primitive Recursive Functions (README)
• μ-Recursive Functions (README)
• Primitive Recursion by Regular Minimalization

• Computable Functions

• Models of Computation

• Turing Machines (README)
• Register Machines
• Partial μ-Recursive Functions (README)
• Turing-Church Thesis
• Kleene Normal Form Theorem (README)
• Indices of Computable Functions (README)

• Beyond Computability

• Decidable and Undecidable Predicates (README)
• Semidecidable Predicates (README)
  • Rice-Shapiro Theorem
• Arithmetical Hierarchy (README)
  • Examples
• Application to Logic: Undecidability and Incompleteness (README)