Turing’s “oracle”: From absolute to relative computability – and back. (English) Zbl 0853.03013

Echeverria, Javier (ed.) et al., The space of mathematics. Philosophical, epistemological, and historical explorations. Revised papers from a symposium on structures in mathematical theories, Donostia/San Sebastian, Basque Country, Spain, September 1990. Berlin: Walter de Gruyter. Grundlagen der Kommunikation und Kognition. 314-348 (1992).
This article examines parts of the history of recursion theory for the last 60 years. The author traces various conceptual routes taken. This differs from other historical surveys in that instead of looking at the different models of absolute computation, this article examines relative computation. The author looks at (1) classical recursion theory over the natural numbers, (2) recursion theory over general structures, and (3) complexity theory. The first item comprises most of the article.
For the entire collection see [Zbl 0839.00019].


03Dxx Computability and recursion theory
03-03 History of mathematical logic and foundations
01A60 History of mathematics in the 20th century
03D10 Turing machines and related notions