# Recursion Theory I

 Title: Recursion Theory I Author: Michael Nedzelsky Submission date: 2008-04-05 Abstract: This document presents the formalization of introductory material from recursion theory --- definitions and basic properties of primitive recursive functions, Cantor pairing function and computably enumerable sets (including a proof of existence of a one-complete computably enumerable set and a proof of the Rice's theorem). BibTeX: @article{Recursion-Theory-I-AFP, author = {Michael Nedzelsky}, title = {Recursion Theory I}, journal = {Archive of Formal Proofs}, month = apr, year = 2008, note = {\url{https://isa-afp.org/entries/Recursion-Theory-I.html}, Formal proof development}, ISSN = {2150-914x}, } License: BSD License Used by: Minsky_Machines Status: [ok] This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.