Theoretical Computer Science - Lecture 12 - μ-recursive functions and Church's thesis

Introduction to Theoretical Computer Science. Lectures as given at Kutaisi International University (Kutaisi, Georgia), during spring semester 2025. Instructor: George Nadareishvili; slides: mostly by Wolfgang Paul. More information can be found at gnadareishvili.com In this lecture, we prove that bounded minimization is primitive recursive, we proceed to define an unbounded μ-operator and define the class of μ-recursive functions. We state Church's thesis. Kutaisi International University: https://www.kiu.edu.ge/ More information about the course and the instructor: https://gnadareishvili.com/