13 - Turing's ‘Oracle’: From Absolute to Relative Computability and Back

Summary

Introduction

We offer here some historical notes on the conceptual routes taken in the development of recursion theory over the last 60 years, and their possible significance for computational practice. These illustrate, incidentally, the vagaries to which mathematical ideas may be susceptible on the one hand, and – once keyed into a research program – their endless exploitation on the other.

At the hands primarily of mathematical logicians, the subject of effective computability, or recursion theory as it has come to be called (for historical reasons to be explained in the next section), has developed along several interrelated but conceptually distinctive lines. While this began with what were offered as analyses of the absolute limits of effective computability, the immediate primary aim was to establish negative results of the effective unsolvability of various problems in logic and mathematics. From this the subject turned to refined classifications of unsolvability for which a myriad of techniques were developed. The germinal step, conceptually, was provided by Turing's notion of computability relative to an ‘oracle’. At the hands of Post, this provided the beginning of the subject of degrees of unsolvability, which became a massive research program of great technical difficulty and combinatorial complexity. Less directly provided by Turing's notion, but implicit in it, were notions of uniform relative computability, which led to various important theories of recursive functionals. Finally the idea of computability has been relativized by extension, in various ways, to more or less arbitrary structures, leading to what has come to be called generalized recursion theory. Marching in under the banner of degree theory, these strands were to some extent woven together by the recursion theorists, but the trend has been to pull the subject of effective computability even farther away from questions of actual computation. The rise in recent years of computation theory as a subject with that as its primary concern forces a reconsideration of notions of computability theory both in theory and practice. Following the historical sections, I shall make the case for the primary significance for practice of the various notions of relative (rather than absolute) computability, but not of most methods or results obtained thereto in recursion theory.