At the intersection of mathematical logic and computational theory, the concepts of completeness, truth, and infinity intertwine to shape our understanding of the capabilities of formal systems. For a formal system to be considered complete, it must be able to prove all propositions that are true under a specific model or interpretation within the system itself. Here, “truth” does not refer to objective reality in everyday experience, but is strictly confined within the semantic framework of the formal system.
However, when formal systems attempt to describe and predict the complexity of the real world, challenges emerge. The inherent uncertainty of the real world — such as the uncertainty principle in quantum mechanics or the sensitive dependence of chaotic systems — often stems from our inability to exhaust all possible states or information, which inherently involves a certain degree of infinity. Therefore, for a formal system to effectively capture and reason about this kind of uncertainty-infused reality, it must possess the capability to handle the concept of infinity. A system that cannot appropriately express or manipulate infinity will face fundamental limitations in describing and predicting the behavior of a complex world.
Lux believes that all computable formal systems cannot fully define infinity and that their incompleteness can be proven using self-referential counterexamples. This assertion touches the core of Gödel’s incompleteness theorems. Computable formal systems based on Turing machines or lambda calculus operate through finite and deterministic steps. Although these systems can simulate infinite computational processes (such as loops), the information they can directly handle and represent at any given moment is always finite.
Gödel precisely leveraged this “finiteness” and the technique of “self-reference” to construct a self-referential proposition within a formal system that includes arithmetic. This proposition essentially claims, “This system cannot prove me.” Due to the system’s finiteness and determinism, it cannot escape its own logical framework to either prove or disprove this proposition about itself.
The issue lies in the fact that computable systems represent and manipulate information through finite strings of symbols and rules. When attempting to express and derive all true propositions about infinite sets or processes, this finiteness becomes an inherent bottleneck. If a system could truly “define infinity” — meaning it could fully capture and prove all truths about infinity — then, in principle, Gödel’s self-referential counterexample should also be encompassed and addressed. But for computable systems, this kind of “exhaustion” is unattainable because the construction of self-reference reveals their intrinsic limitations in expressing their own metamathematical properties, rather than merely a simple lack of definition of infinity.
In the face of this intrinsic incompleteness of computable formal systems, transfinite methods offer a unique strategy. Lux believes this is a way to “approximate infinity through the logical craftsmanship of natural sciences to address the deficiencies of computable formal systems.” This perspective is highly insightful.
Cantor’s theory of transfinite numbers reveals the different “sizes” or “levels” of infinity, providing systematic tools for thinking about and operating on infinite sets. Turing, in his doctoral thesis, practiced this strategy of “approaching infinity” by introducing oracle machines and transfinite induction.
An oracle machine is defined as an abstract mechanism capable of providing “answers” that exceed the computational power of a Turing machine. It can be viewed as an external, non-computable “source of truth,” conceptually akin to the knowledge we obtain from observation, experimentation, or non-algorithmic intuition — knowledge not derived solely from deterministic computation.
Transfinite induction allows reasoning over ordinal numbers beyond finite steps, thereby constructing logical systems with derivational capabilities that exceed those of standard Turing machines. This does not directly “solve” Gödel’s incompleteness, but rather, at a higher level, extends the system’s range of decidability by introducing external information and transfinite iteration. It acknowledges the inherent limitations of formal systems and seeks to enhance the system’s “cognitive” or “certainty” capabilities through a progressive, iterative strategy to deal with “truth” and “uncertainty” that traditional computable systems cannot fully capture. This reflects a more pragmatic logical strategy oriented toward the complexity of the real world.
