Recursion Theory I

Michael Nedzelsky

April 5, 2008

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

License

BSD License

Topics

Session Recursion-Theory-I

Used by