In the late 1930s Alan M. Turing was one of the founders of computability theory. His main contributions to this field were published in three papers that appeared in the span of a few years, and especially in his ground-breaking 1936–1937 paper, published when he was twenty-four years old.

As indicated by its title, "On Computable Numbers, with an Application to the Entscheidungsproblem," Turing's paper deals ostensibly with real numbers that are computable in the sense that their decimal expansion "can be written down by a machine." As he pointed out, however, the ideas carry over easily to computable functions on the integers or to computable predicates.

The paper was based on work that Turing had carried out as a Cambridge graduate student, under the direction of Maxwell Newman (1897–1984). When Turing first saw a 1936 paper by Alonzo Church, he realized at once that...