Mechanised Computability Theory

Date

Authors

Norrish, Michael

Publisher

Springer

Abstract

This paper presents a mechanisation of some basic computability theory. The mechanisation uses two models: the recursive functions and the λ-calculus, and shows that they have equivalent computational power. Results proved include the Recursion Theorem,

Keywords

Keywords: Computability theory; Computational power; Mechanisation; Recursions; Recursively enumerable sets; Universal machines; Calculations; Computability and decidability; Machinery; Mechanization; Problem solving; Recursive functions; User interfaces; Theorem p

URI

http://hdl.handle.net/1885/36846

Collections

ANU Research Publications

Source

Mechanised Computability Theory

Type

Conference paper

DOI

10.1007/978-3-642-22863-6_22

Restricted until

2037-12-31

Downloads

File

Description

01_Norrish_Mechanised_Computability_2011.pdf (272.33 KB)