Logic and learning: Turing’s legacy

Abstract

Abstract Turing’s best known work is concerned with whether universal machines can decide the truth value of arbitrary logic formulae. However, in this paper it is shown that there is a direct evolution in Turing’s ideas from his earlier investigations of computability to his later interests in machine intelligence and machine learning. Turing realised that machines which could learn would be able to avoid some of the consequences of Godel’s and his results on incompleteness and undecidability. Machines which learned could continuously add new axioms to their repertoire. Inspired by a radio talk given by Turing in 1951, Christopher Strachey went on to implement the world’s first machine learning program. This particular first is usually attributed to A.L. Samuel. Strachey’s program, which did rote learning in the game of Nim, preceded Samuel’s checker playing program by four years. Neither Strachey’s nor Samuel’s system took up Turing’s suggestion of learning logical formulae. Developments in this area were delayed until Gordon Plotkin’s work in the early 1970’s. Computer-based learning of logical formulae is the central theme of the research area of Inductive Logic Programming, which grew directly out of the earlier work of Plotkin and Shapiro. In the present paper the author describes the state of this new field and discusses areas for future development.