On Programmatic Aspects of the Universality, Parameter, and Recursion Theorems of Classical Computability

Abstract

The Universality, Parameter, and Recursion Theorems are three foundational results of classical computability theory. We show how these theorems can be programmatically illustrated and partially validated in Lisp. Our programs can be used as supplementary materials to texts on theoretical computer science, mathematical logic, or metamathematics.

Keywords

• computability theory
• universality theorem
• parameter theorem
• recursion theorem
• recursion theory
• lisp