Alan Mathison Turing

*Proceedings of the London Mathematical Society* s2-45(1), pages 161–228

1939

The well-known theorem of Godel (Godel [1], [2]) shows that every system of logic is in a certain sense incomplete, but at the same time it indicates means whereby from a system L of logic a more complete system L' may be obtained. By repeating the process we get a sequence L, L1 = L', L2 = L1', ... each more complete than the preceding. A logic Lw may then be constructed in which the provable theorems are the totality of theorems provable with the help of the logics L, L1, L2, .... We may then form L2w related to Lw in the same way as Lw was related to L. Proceeding in this way we can associate a system of logic with any constructive ordinal. It may be asked whether a sequence of logics of this kind is complete in the sense that to any problem A there corresponds an ordinal a such that A is solvable by means of the logic La. I propose to investigate this question in a rather more general case, and to give some other examples of ways in which systems of logic may be associated with constructive ordinals.