The Princeton Ordinal Hierarchies
Alonzo Church's Lambda Calculus, Emil Post, and Oracle Machines Over the Abyss
Across the Atlantic in April 1936, Alan Turing handed the completed typescript of On Computable Numbers to Max Newman at Cambridge. That same month, a journal offprint arrived from Princeton University. Working with his former doctoral students Stephen Cole Kleene and J. Barkley Rosser, American logician Alonzo Church had just published An Unsolvable Problem of Elementary Number Theory in the American Journal of Mathematics. Church used a formal system of function abstraction and variable substitution called the $\lambda$-calculus. Having proved its equivalence to Kurt Gödel and Jacques Herbrand's general recursive functions, Church had already reached the exact same negative conclusion to David Hilbert's Entscheidungsproblem.
At first glance, the simultaneous publication threatened to prevent Turing's paper from appearing in the Proceedings of the London Mathematical Society. Yet when Newman examined both arguments, he saw a vital difference. When Gödel himself read Church's $\lambda$-calculus paper at the Institute for Advanced Study, Gödel remained unconvinced that $\lambda$-definability captured all possible mechanical calculations. Turing's paper tape and scanning head, by contrast, modeled the physical act of human calculation directly. Gödel immediately accepted Turing's definition as definitive. Simultaneously in New York, logician Emil Post independently formulated an equivalent worker-and-boxes model in 1936.
Newman wrote to the London Mathematical Society and to Church at Princeton urging publication. Meanwhile, Turing added a concise technical appendix proving that every $\lambda$-definable function is computable by a Turing machine and vice versa. Sailing to New York aboard the steamer Berengaria in late September 1936, Turing enrolled at Princeton University to pursue a doctorate under Church's supervision. At Princeton's Fine Hall—which housed both the university mathematics department and the newly created Institute for Advanced Study—Turing worked down the corridor from Albert Einstein, John von Neumann, Hermann Weyl, and Oswald Veblen.
For his doctoral research between 1936 and May 1938, joined in friendly debates by fellow Cambridge expatriate Maurice Pryce, Turing investigated a deep question. Could mathematicians escape Gödel's incompleteness theorem by iterating formal systems across the transfinite ordinal numbers? His 1938 Princeton dissertation, Systems of Logic Based on Ordinals (published in 1939), established four foundational structures in mathematical logic:
- * Transfinite progression of formal systems: Starting from an incomplete base arithmetic $L_0$, one adds its unprovable true Gödel sentence $G_0$ to form a stronger system $L_1$. One repeats the step through $L_2, L_3, \dots$ and collects the union at the first infinite limit ordinal $\omega$ to form $L_\omega$.
- * Constructive ordinal notations: To keep the hierarchy anchored to syntax rather than abstract set theory, Turing required that every transfinite index $\alpha$ be represented by a concrete Turing machine description number.
- * The boundary of mechanical intuition: Turing proved that any true number-theoretic statement of standard universal form ($\forall x R(x)$) becomes provable at stage $\omega + 1$. However, no mechanical rule can identify which machine description number represents the ordinal $\omega + 1$.
- * The $O$-machine (oracle machine): In a brief two-page section of the dissertation, Turing defined an ordinary Turing machine augmented with a black-box oracle. That oracle answers an uncomputable query, such as whether any given machine halts, in a single step.
Even when armed with an instantaneous halting oracle, Turing showed by a second diagonal argument that the new $O$-machine immediately confronts its own higher-order halting problem. Although John von Neumann offered Turing a postdoctoral assistantship at the Institute for Advanced Study in the spring of 1938 at an annual salary of fifteen hundred dollars, Turing declined and returned to Cambridge that summer. In 1944, American logician Emil Post transformed Turing's 1938 oracle machine into the formal theory of Turing reducibility and degrees of unsolvability, mapping an infinite hierarchy of mathematical problems that even a halting oracle cannot untangle.