formal undecidability

Compiled with AI assistance and selectively reviewed. Please consult the cited passages; the books remain the authoritative source. About this companion

Editorial synthesis · provisional

Definition

Formal undecidability is a system-relative limit on proof or uniform algorithmic decision. The corpus distinguishes it from unsettled physical outcomes and incomplete observations. Gödel, Turing and Chaitin supply different precise examples concerning arithmetic proof, program termination and incompressibility claims. Their results constrain what suitable formal frameworks can establish; they do not imply that every particular question is unknowable or that reality becomes random because a language cannot decide it.

Explanation

RB1 describes Gödel’s setting as consistent, effectively axiomatizable and sufficiently expressive for arithmetic. The scope conditions matter: the result concerns what can be proved within such a system, not the collapse of logical reasoning or a demonstration that any arbitrarily chosen sentence is undecidable. PB’s compressed formulation is accompanied by an explicit separation of account-limits from worldly openness.

Turing’s example concerns a uniform procedure deciding termination for every program and input, not an inability to establish the behavior of any individual program. Chaitin’s separate result bounds what a sound system can establish about particular strings’ incompressibility through its axiomatic information. These are exact types of limitation, not interchangeable claims about computational inconvenience.

Da Costa and Doria’s discussion extends the issue to sufficiently rich mathematical presentations of physical law, where global properties may resist general algorithmic classification despite specified equations. The manuscript labels this formal rather than ontic indeterminacy. The proposed entry therefore does not derive an open physical future merely from an undecidable proposition in an account of it.

Scope and attribution

Preserve the stated hypotheses and distinguish the different formal limitations.

PB — The Possible Book

Compressed incompleteness statements are expressly separated from openness in the world.

Occurrence locators: 94, 147, 157, 164, 182, 183.

RB1 — The Real Book, Volume I: The Possible Is Real

The formal taxonomy, axiomatization conditions and distinct Gödel-Turing-Chaitin limits remain explicit.

Occurrence locators: 120, 121, 127, 128, 129, 130, 131.

RB3 — The Real Book, Volume III: Murmurations

Source-verified occurrence; see the printed-page references below.

Occurrence locators: Notes: 393, 394; Epilogue: 355.

Background used in the editorial explanation

Named theories and mechanisms are distinguished from neighboring background, homonyms and the author’s own synthesis. Reproduced AI passages retain their separate voice.