At the intersection of mathematical logic and computational theory, the concepts of completeness, reality, and infinity intertwine, shaping our understanding of the capabilities of formal systems. For a formal system to be deemed complete, it means that all propositions that are true under a specific model or interpretation can be proven within that system. Here, 'truth' does not refer to objective reality in everyday experience, but is strictly confined within the semantic framework of that formal system.
The uncertainty of the real world and the necessity of infinity
However, challenges arise when formal systems attempt to depict and predict the complexities of the real world. The inherent uncertainty of the real world, such as the uncertainty principle in quantum mechanics or the sensitive dependence in chaotic systems, often stems from our inability to exhaustively account for all possible states or information, which contains some degree of infinity. Therefore, for a formal system to effectively capture and reason about this 'real' uncertainty, it must possess the ability to handle concepts of infinity. A system that cannot appropriately express or operate on infinity will face fundamental limitations when describing and predicting the behaviors of a complex world.
The inherent incompleteness of computable formal systems
Lux argues that all computable formal systems cannot fully define infinity, and thus self-referential counterexamples can be used to demonstrate their incompleteness. This assertion touches on the core of Gödel's incompleteness theorem. Computable formal systems based on Turing machines or Lambda calculus essentially operate in finite steps and deterministically. Although these systems can simulate infinite computational processes (such as loops), the information they can directly process and represent at any given moment is always finite.
Gödel utilized this technique of 'finiteness' and '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 prove or disprove this proposition about itself.
Why is it difficult for computable systems to 'define infinity' and lead to incompleteness?
The problem is that computable systems represent and operate on information through finite strings of symbols and rules. When attempting to express and derive all true propositions about infinite sets or processes, this finiteness constitutes an inherent bottleneck. If a system could truly 'define infinity,' meaning it could completely capture and prove all truths about infinity, then in principle, the self-referential example constructed by Gödel should also be included and addressed. However, for computable systems, this 'exhaustion' is unattainable, because the self-referential construction reveals their inherent limitations in expressing their own metamathematical properties, rather than simply lacking a definition of infinity.
Transfinite methods: a strategy to approach the infinite
Confronted with the inherent incompleteness of computable formal systems, **Transfinite** methods provide a unique strategy. Lux believes that this is a way to 'approach the infinite using the logical craftsmanship of natural sciences to address the incompleteness flaws of computable formal systems.' This viewpoint is enlightening.
Cantor's theory of transfinite numbers reveals the different 'sizes' or 'levels' of infinity, providing us with systematic tools to think about and operate on infinite sets. Turing, in his doctoral thesis, practically applied this 'approach to infinity' strategy by introducing oracle machines and transfinite induction.
An oracle machine is defined as an abstract mechanism that can provide 'answers' that transcend the computational capabilities of Turing machines, and can be seen as an external, non-computable 'source of truth.' This conceptually resembles the knowledge we gain from observation, experimentation, or non-algorithmic intuition, which are not derived solely through deterministic computation.
Transfinite induction allows reasoning over ordinals that transcend finite steps, thereby constructing logical systems with derivation capabilities that exceed standard Turing machines. This does not directly 'solve' Gödel's incompleteness, but rather, at a higher level, expands the system's decidability by introducing external information and transfinite iteration. It acknowledges the limitations of formal systems themselves and attempts to enhance the system's 'cognitive' or 'certainty' abilities through a progressive, iterative strategy to tackle the 'realities' and 'uncertainties' that traditional computable systems cannot fully capture. This embodies a more pragmatic logical strategy oriented towards the complexities of the real world.
