A Swiss Pocket Knife for Computability
A. Banerjee, O. Danvy, K. -g. Doh, J. Hatcliff (eds, Neil D. Jones · 2016
This research is about operational- and complexity-oriented aspects of classical foundations of com-putability theory. The approach is to re-examine some classical theorems and constructions, but with new criteria for success that are natural from a programming language perspective. Three cornerstones of computability theory are the S-m-n theorem; Turing’s “universal machine”; and Kleene’s second recursion theorem. In today’s programming language parlance these are respec-tively partial evaluation, self-interpretation, and reflection. In retrospect it is fascinating that Kleene’s 1938 proof is constructive; and in essence builds a self-reproducing program. Computability theory originated in the 1930s, long before the invention of computers and pro-grams. Its emphasis was on delimiting the boundaries of computability. Some milestones include