The developments of the concept of machine computability from 1936 to the 1960s

Jean Mosconi

pp. 37-56

in: Jacques Dubucs, Michel Bourdeau (eds), Constructivity and computability in historical and philosophical perspective, Berlin, Springer, 2014

Abstract

From the 1940s to the 1960s, despite the significant work done on recursive functions (properly) and later on the lambda-calculus, the theory of calculability was developed more and more as a theory of computation by an idealized machine, or in the form of a general theory of algorithms. I will only deal here with the former aspect, a development that stems from the concepts introduced in 1936 by Turing. I will try to show how Turing's ideas were gradually adopted, developed and modified. The Turing machine had an increasingly important role and was the object of systematic investigation. It was subsequently reworked to such an extent that a new model of machine was fashioned, the program and register machine. However, the initial model kept a significant place, and extensions of Turing's analysis led, toward the end of the century, to profound reflections about the notion of a constructive object and the general notion of an algorithm.