Turing in the Land of O(z)
Solomon Feferman · 1990
Abstract After having published his fundamental and justly famous paper “On Computable Numbers, with an Application to the Entscheidungsproblem” (1936- 3 7), followed in 1937 by a detailed proof of the equivalence between his notion of computability and Church’s notion of λ -definability, Alan Turing produced a third quite distinctive and substantial paper in mathematical logic, entitled “Systems of Logic Based on Ordinals” (1939). There Turing took up quite systematically the natural idea of trying to overcome the Godelian incompleteness of formal systems, by means of transfinite iteration of principles which serve to overcome incompleteness locally.