Alan Turing’s Doctoral Thesis “Systems of Logic Based on Ordinals” and Its Modern “Echoes”

Alan Turing’s 1938 doctoral thesis Systems of Logic Based on Ordinals, completed under the supervision of Alonzo Church, represents his groundbreaking work in the field of mathematical logic and computability theory. This thesis not only deepened his earlier research on Turing machines but also explored the implications of Gödel’s incompleteness theorems in depth, introducing the highly influential concept of the “oracle Turing machine.” Fascinatingly, these theoretical abstractions from nearly a century ago seem to have found unexpected practical grounding and concrete analogies in modern distributed systems like Bitcoin, showcasing the profound vitality of foundational theories.

Thesis Background and Motivation

In the 1930s, the mathematics community was shaken by Kurt Gödel’s incompleteness theorems published in 1931. Gödel proved that any sufficiently powerful formal axiomatic system (such as one capable of expressing arithmetic) must contain true propositions that cannot be proven or disproven within the system itself. This implied that a single, complete, and consistent formal system encompassing all mathematical truths was impossible.

Turing’s 1936 paper On Computable Numbers, with an Application to the Entscheidungsproblem introduced the Turing machine model and demonstrated the undecidability of the halting problem and the Entscheidungsproblem. This laid the foundation for computability theory, clarifying what it means for something to be “computable.” However, Gödel’s theorems raised a question: If some true propositions cannot be proven within a given system, is it possible to “transcend” this limitation by constructing a more powerful logical system?

Turing’s doctoral thesis aimed to respond to this question by exploring the limits beyond standard Turing machine computability. He attempted to overcome Gödelian incompleteness by “iteratively adding axioms” or introducing more powerful, non-mechanical steps.

Thesis Content and Its Profound Connection to Bitcoin

The core of Systems of Logic Based on Ordinals lies in the introduction of ordinals and oracle Turing machines to construct “ordinal logic” and explore relative computability.

1. Oracle Turing Machines and the Elegant Analogy with POW Miners:

Turing’s oracle Turing machine is a theoretical extension that includes a special “oracle” capable of instantly answering membership queries for a specific set, whether computable or not. The oracle itself “cannot be a machine.”

In Bitcoin’s Proof-of-Work (PoW) mechanism, each PoW miner can be seen as a “relative” oracle Turing machine. Every miner is attempting to solve a computational puzzle (finding a hash that meets specific conditions) that is hard to compute but easy to verify.
When a miner successfully finds a solution to a block, they broadcast it to the network. For other miners, this newly discovered solution (the new block) becomes like an “oracle”—instantly providing the answer they were seeking: the valid hash of the current block. They no longer need to perform the intensive computation themselves; they simply verify its validity and begin mining the next block.
This mechanism perfectly illustrates relative computability: a computationally hard problem for one miner becomes relatively computable (verifiable) once another miner finds the solution and broadcasts it.

2. Longest Chain Rule as a Practical Implementation of Transfinite Iteration:

Turing used ordinals in his thesis to build an infinite sequence of logical systems, continuously extending the system’s capabilities through transfinite recursion—an effort to infinitely improve a system’s “completeness.” He envisioned a hierarchy where each level is “more complete” or “stronger” than the one before.

Bitcoin’s Longest Chain Rule is a practical embodiment of this transfinite iteration. The blockchain is a continually growing chain, with each new block extending and confirming the previous one.
“Longest” not only refers to accumulated PoW but also reflects the strength of consensus over transaction history. When forks occur, the network chooses the chain with the most accumulated work—representing more “history” and “consensus.” This process can be seen as a transfinite iteration toward a more “solidified” state, even if it can theoretically never reach a true “endpoint” (since the chain can extend indefinitely).

3. UTXO/Timestamp Chain—An Infinite Sequence Logical System:

Turing’s thesis aimed to construct an “infinite sequence logical system” to encompass more and more mathematical truths.

In Bitcoin, the UTXO (Unspent Transaction Output) chain forms a rigorous logical system of digital asset ownership. Each UTXO represents a state generated by a previous transaction and transferred through digital signatures. This chain precisely defines who owns what and how it can be spent.
The timestamp chain—i.e., the blockchain itself—is an immutable, time-ordered sequence of transaction records. Each block includes a timestamp and links to the previous block, forming a continuous and increasing sequence.
Together, these constitute Bitcoin’s “infinite sequence logical system”: UTXOs ensure the logical correctness of ownership, while the blockchain ensures its chronological order and immutability. Together, they build an infinitely extensible, self-sustaining economic logic system.

4. The PH Structure Formed by UTXO/PoW/Longest Chain and the Recursive Reduction in Turing Degrees:

Turing’s concept of Turing degrees classifies problems by their “degree of uncomputability,” using relative computability (i.e., solving one problem given an oracle for another) to define their relationships. In complexity theory, the Polynomial Hierarchy (PH) also relies on this notion to define relationships among different complexity classes.

UTXO Layer (Base-Level Computability): Represents asset ownership and transaction verifiability, which are computationally efficient and verifiable. This aligns with P (polynomial-time solvable) or NP (polynomial-time verifiable) problems.

PoW Layer (Computational Difficulty): Represents the computational difficulty of finding new blocks, requiring substantial non-parallelizable brute-force computation. This aligns with NP-complete or NP-hard problems—difficult to solve but easy to verify. The solution found by one miner acts as an “oracle” for others, turning the previously hard problem into an easy one.

Longest Chain Rule Layer (Higher-Level Consensus Complexity): Resolves network consensus and the immutability of history. When conflicts or forks arise, the network chooses the chain with the most accumulated work—essentially solving the uncertainty of “which chain is real.” This resembles higher complexity classes that achieve “effective” consensus by relying on the lower-level PoW “oracles.”

The Bitcoin system can be understood as a three-tier PH structure composed of UTXO, PoW, and the Longest Chain Rule. It demonstrates a recursive reduction between the computable and uncomputable under Turing degree paradigms.

Far-Reaching Influence of the Thesis

While Systems of Logic Based on Ordinals didn’t define a computer model like Turing’s 1936 paper, it had an equally profound impact on theoretical computer science:

Advanced the Development of Computability Theory and Recursion Theory: The oracle Turing machine became a powerful tool for studying the limits of computation and the relationships between different computational models.

Laid the Foundation for Complexity Theory: The concept of relative computability provided a framework for comparing problem “difficulty,” influencing the formation of key concepts in computational complexity theory such as the Polynomial Hierarchy (PH). The P vs NP problem—whether every problem verifiable in polynomial time is also solvable in polynomial time—is central to complexity theory. Oracle Turing machines are widely used to define different complexity classes and prove their relationships (e.g., NP can be defined using a deterministic Turing machine with an NP oracle).

Impact on Cryptography and Distributed Systems in Practice: Although purely theoretical, Turing’s insights into computational hardness and undecidability indirectly influenced the foundations of modern cryptography. For instance, Bitcoin relies on computationally “hard problems” (like hash puzzles), which are difficult to solve but easy to verify. This asymmetry is deeply connected to how complexity theory categorizes problems. The PoW mechanism in Bitcoin—finding a specific hash—is computationally expensive but quickly verifiable, echoing the traits discussed in Turing’s and complexity theory, even though Turing did not foresee digital currency. His theoretical framework provided a solid foundation for such systems.

Early Exploration of Hypercomputation: Though hypercomputation remains controversial in physical implementation, Turing’s thesis was one of the earliest theoretical attempts to explore capabilities beyond traditional Turing machines, showcasing his profound insight into foundational mathematical problems.

Refined Understanding of Gödel’s Incompleteness Theorems: The thesis demonstrated that incompleteness is not an “end,” but rather something that can be continuously approached by constructing more powerful systems—even if they too remain incomplete—thus advancing the boundary of logical reasoning.

In summary, Turing’s doctoral thesis is a highly theoretical yet profoundly important work. It not only responded to the challenges posed by Gödel’s incompleteness theorems, but also introduced the concepts of oracle Turing machines and ordinal logic, offering new perspectives and tools to understand the nature and limits of computation—and how to potentially transcend them. Its influence extends beyond pure mathematical logic, finding unexpected “echoes” and “concretizations” nearly a century later in practical fields like modern computational complexity theory and emerging blockchain technologies such as Bitcoin, showcasing Turing’s extraordinary insight.