‍Introduction

Between Gödel’s incompleteness theorems and Turing’s theory of computability lies a profound logical corridor—one that connects the computational boundaries of formal systems with the judgment limits of real-world systems. This article explores Bitcoin’s UTXO model from the perspective of Turing Machines and Oracle Machines, aiming to unify “decidability problems” and the “P/NP problem” into a broader logical framework through the concept of ordinals.

I. Computability and the Turing Machine: The Boundaries of Formalized Computation

In his 1936 paper, Turing introduced the Turing Machine—the first clearly defined model of computability. It formalized the description of all “effectively computable” processes. In this sense:

• Turing Machine = Formal system of computability;
• Bitcoin’s UTXO construction process—such as input referencing, signature verification—is a mechanical computation executable by a Turing Machine;
• Script execution and transaction input-output logic are all examples of “Turing-computable” processes.
  

Turing Machines handle problems that are fully computable within formal systems.

II. Ordinals and Oracle Machines: Relative Computability and Decidability

In his 1938 doctoral dissertation, Turing introduced the concept of ordinals and the Oracle Turing Machine. Unlike ordinary Turing Machines, Oracle Machines can query an external “oracle” to resolve problems that standard Turing Machines cannot decide.

• Ordinals provide Oracle Machines with “decision hierarchies,” enabling them to handle problems across formal systems;
• Oracle Machine = System of relative computability;
• Decision problems—like double-spend detection and longest chain selection—fall into this category.
  

Oracle Machines deal with how to relatively determine truth across systems.

III. The Logical Structure of the Bitcoin System: Intersection of Computation and Decision

Bitcoin’s UTXO model can be viewed as a formal system at the Turing Machine level—its operation is fully computable. However, issues in the consensus mechanism like double-spend judgment and longest-chain induction fall into the realm of non-formal-system problems. These involve comparisons across nodes and historical states and require higher-level decision mechanisms.

Thus, the Bitcoin system is a composite operational structure of both Turing and Oracle Machines:

• Turing Machines support the transaction layer;
• Oracle Machines support the consensus layer.

IV. From Ordinals to the P/NP Problem: A Unified View of Complexity Theory

In classical complexity theory, the P/NP problem is a longstanding open question. This article proposes a unified perspective: the P/NP problem is essentially a complexity version of the decidability problem across systems.

• Decidability Problem: Whether an algorithm exists to determine truth for all inputs;
• P/NP Problem: Whether a polynomial-time Turing Machine solution exists;
• Both fall within the problem space solvable by Oracle Machines.
  

Ordinals provide the logical scaffolding for complexity stratification, unifying decidability and complexity assessments.

V. Gödel, Sets, and Foundational Philosophical Reflections

Why did Gödel study set theory? His goal was to unify reality and logic—constructing the foundations of the world through logically definable “sets.”

• Set = Conceptualizable basic unit;
• Cardinality = Number of elements in a set; it’s the unit in computable systems;
• Ordinal = Represents hierarchical relationships; it’s the unit in decidable systems.
  

For example: The set {apple, chestnut, banana} has a cardinality of 3. But logical determinations within the system—like whether it’s consumable or whether it follows an order—require ordinal support.

Conclusion: A Unified View of the Logical World

By distinguishing between Turing Machines and Oracle Machines, this article unifies computational problems, decision problems, consensus problems, and complexity problems within a single logical structure. This not only helps us understand the operational boundaries of real systems like Bitcoin, but also provides a new lens to re-examine the P/NP question, Gödel’s ordinals, and the limits of formal systems.

• Computable problems belong to Turing Machines
• Decidable problems belong to Oracle Machines
• P/NP problems are complexity-based expressions of decision problems
• Bitcoin is a natural computational platform fusing Turing and Oracle system logic