Recursion Theory I

Michael Nedzelsky

April 5, 2008

This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.


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