Recursion Theory I

Michael Nedzelsky

April 5, 2008


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).


BSD License


Session Recursion-Theory-I

Used by