Trustworthy Systems

Mechanised computability theory


Michael Norrish


Australian National University


This paper presents a mechanisation of some basic computability theory. The mechanisation uses two models: the recursive functions and the lambda-calculus, and shows that they have equivalent computational power. Results proved include the Recursion Theorem, an instance of the s-m-n theorem, the existence of a universal machine, Rice's Theorem, and closure facts about the recursive and recursively enumerable sets. The mechanisation was performed in the HOL4 system and is available online.

BibTeX Entry

    address          = {Nijmegen, The Netherlands},
    author           = {Norrish, Michael},
    booktitle        = {International Conference on Interactive Theorem Proving},
    doi              = {10.1007/978-3-642-22863-6_22},
    editor           = {{Marko van Eekeln, Herman Geuvers, Julien Schmaltz, Freek Wiedijk}},
    month            = aug,
    pages            = {297---311},
    paperurl         = {},
    publisher        = {Springer},
    slides           = {},
    title            = {Mechanised Computability Theory},
    year             = {2011}