Truth Without Proof? Gödel, Turing, and Algorithmic Information

A machine can spend forever refusing to tell you whether it will run forever.

Imagine a physical Turing machine: a tape, a head, a finite controller, simple deterministic rules. Ask one yes-or-no question: will it ever halt? If it halts, the answer eventually arrives as an event. If it does not halt, waiting gives you something very different. At every finite time the machine has merely failed to halt so far. There is no final instant called “infinity” at which the machine flashes a light saying: it will never halt.

What, then, does it mean to say that the answer was already “no” all along?

Classical mathematics normally answers without hesitation: the machine either halts or it does not. Our ignorance changes nothing. But the apparently harmless phrase “there is a fact of the matter” contains a philosophy. Gödel and Turing did not prove that philosophy. They proved precise limitations on formal derivation and effective procedure. Whether every unresolved proposition nevertheless possesses an observer-independent truth value is a further question.

Four questions hiding inside one word

It is useful to separate four notions that everyday mathematical language constantly slides together.

Truth is semantic. A sentence is true in a mathematical structure or model. Proof is syntactic: a sentence follows from specified axioms by specified rules. Computability asks whether a finite algorithm can return the correct answer for every admissible input. And observer access asks whether a finite agent can actually obtain or certify the answer using finite time, memory, measurements, and formal resources.

These distinctions are not philosophical decoration. They are exactly where the popular interpretation of Gödel goes wrong.

What Gödel actually showed

Take a consistent, effectively axiomatized formal theory F strong enough to express elementary arithmetic. In the Gödel–Rosser form of the first incompleteness theorem, there is a sentence of the language of F that is neither provable nor refutable in F. The crucial words are “in F.” Gödelian incompleteness is first of all a theorem about derivability relative to a specified formal system.

That is weaker — and more precise — than the slogan “Gödel proved that there are truths that can never be proved.” A stronger theory may settle a sentence that was independent of F; the stronger theory will then have independent sentences of its own. There is no final effective formal theory that closes the process. But the theorem does not place a metaphysical stamp reading forever unknowable on one particular sentence.

The familiar phrase “true but unprovable” introduces an extra semantic step. One evaluates the sentence in an intended mathematical structure — for arithmetic, usually the standard natural numbers — and then contrasts that semantic judgment with what F can derive. The incompleteness theorem itself is syntactic; the attribution of truth is model-relative semantics layered on top.

Model theory makes the point vivid. If a sentence is independent of a first-order theory F, then, under the usual consistency assumptions, there are models of F in which the sentence holds and models in which its negation holds. Incompleteness therefore does not force us to imagine one sentence floating in a unique mathematical universe, secretly colored “true” but inaccessible to proof. It also permits a very different picture: several legitimate mathematical structures in which different answers hold.

You can be a Platonist without believing in one mathematical universe

This is the point that often gets lost. Mathematical Platonism is usually introduced as belief in a mind-independent realm of mathematical objects. But realism about mathematical structures does not force realism about one uniquely privileged mathematical universe.

There are explicitly pluralist forms of Platonism. Mark Balaguer’s “full-blooded” or plenitudinous Platonism allows a multiplicity of mathematical universes rather than one privileged totality. In set theory, Joel David Hamkins has argued for a multiverse view: many distinct concepts of set, each instantiated in a corresponding universe. Hamkins is not trying to make mathematics less real. Quite the contrary: on the multiverse picture, the alternative universes are themselves genuine mathematical worlds. The Stanford Encyclopedia of Philosophy explicitly notes that Platonism need not entail that every set-theoretic proposition has one determinate truth value, and describes plenitudinous Platonism as postulating multiple mathematical universes corresponding to consistent theories.

This gives us a third position between simple classical absolutism and anti-realism:

Truth then becomes indexed to structure. The continuum hypothesis is true in some set-theoretic universes and false in others. That does not mean “anything goes.” A theorem proved from axioms T is, by the soundness theorem, true in every model of T. If T is consistent, first-order completeness connects that syntactic consistency to the existence of models. Proof does not manufacture truth; it identifies what is invariant across the models satisfying the assumptions.

So I would sharpen the tempting phrase “a proposition is true in some model if a formal system proves it.” The correct relation is stronger and cleaner: if T ⊢ P, then P holds in every model of T. If P is independent of T, then the theory does not select between models on opposite sides. A pluralist Platonist may take both structures seriously rather than insisting that one of them must be the uniquely intended universe.

There are nuances. One may be pluralist about set theory while retaining a privileged conception of ordinary arithmetic; multiverse views need not erase every form of mathematical absoluteness. Solomon Feferman, from a different philosophical direction, argued that the continuum hypothesis may not even be a “definite mathematical problem,” while treating many ordinary mathematical questions much more robustly. The important point is simply that rejecting a single global truth assignment is not equivalent to rejecting mathematical reality.

Turing turns the issue into an experiment

Gödel’s theorem concerns proof systems. Turing’s halting theorem concerns algorithms. There is no total procedure that, given an arbitrary program and input, always halts and correctly says whether the program itself eventually halts.

The asymmetry is operational. If the computation halts, there is a finite witness: wait and eventually observe the halt. If it does not halt, direct simulation never reaches a stage that certifies non-halting. Particular non-halting programs can of course be settled by additional reasoning. What does not exist is one terminating method that settles every program.

A classical realist says that every individual halting proposition nevertheless has a Boolean truth value. A constructive interpretation need not treat an unresolved proposition as a hidden bit already waiting behind the curtain. A pluralist realist can take yet another route: truth is fully objective inside specified mathematical structures, while refusing to posit one unqualified universe in which all such semantic questions are globally settled.

Gödel and Turing force none of these philosophies on us. Their results survive under all of them because their operational content is about what fixed systems of proof and computation can guarantee.

The physical version makes the problem sharper

Build the Turing machine physically. Now the question “will it ever halt?” is also a question about a physical system. Does an observer-independent physical fact exist even when no finite observation can establish it?

A scientific realist may answer yes. An operationalist may ask what empirical operation gives content to the distinction. And in idealized infinite-system physics the issue becomes even harder: the mathematical model may assign an exact property that no physical observer could measure with arbitrary precision or establish in finite time.

Results such as the undecidable Ising observables of Gu and collaborators or the undecidable spectral gap exploit an unbounded computational resource in the physical family, often through an infinite or thermodynamic-limit construction. They make a macroscopic property depend on the behavior of an embedded universal computation. A crucial contrast is that fixed finite versions return to computability in principle: a finite-tape machine has finitely many configurations, and a fixed finite quantum system is represented by finite-dimensional data. The undecidability enters when the family supplies the unbounded resource.

This is different from the algorithmic-construction barriers we have been studying in Kolmogorov Theory. There the physical experiment and observed record can remain finite. The unboundedness sits instead in the space of possible descriptions and in their possible running times. The physical world need not contain an infinite tape; the observer’s universal search over candidate programs effectively does.

Kolmogorov complexity hides the same philosophical choice

Algorithmic information theory makes the issue unusually transparent. Standard AIT defines the Kolmogorov complexity of a finite string x by

Textbooks then speak as though K(x) were simply a number attached to x. Classically, that is natural. A literal-printing program ensures that at least one description exists; one takes the least length among all descriptions.

But constructively, this packaging is not innocent. To know that a given length is minimal means ruling out all shorter programs — including programs whose computations may never halt. Recent constructive formalizations make this explicit. Forster, Kunze, and Lauermann develop Kolmogorov complexity in Coq without simply postulating a total numerical K-function. They work with functional relations, and they point out that the general principle giving least elements of arbitrary inhabited predicates is equivalent, in their setting, to the law of excluded middle. They also note that classical formalizations such as the HOL4 work of Catt and Norrish use a least-element operator together with classical logic and choice.

This is philosophically revealing. The operational content of compression begins one level below the number K(x).

That statement asks for a finite witness. If a short program exists and halts, we can eventually exhibit it. We do not need to first possess the metaphysical object “the exact complexity of x.”

AIT can work relationally

This observation is more than philosophical housekeeping. A surprising amount of the machinery can be reformulated in terms of relations among finite descriptions.

Instead of saying

say directly:

Instead of treating optimality as access to a hidden number K(x), compare two explicit programs. If a new program is shorter and prints the same data, it is a finite witness that the old description was not optimal.

This relational view is especially natural for the three barriers in our work on algorithmic emergence.

The first barrier can be read as a counting statement: for most records in the witness family, no conditional program shorter than a specified threshold exists. The second says that even when a shorter program exists, no total constructor is guaranteed to find one in every case. The third can be stated without mentioning the exact value of K at all: for every total valid constructor and every proposed margin, there are compressible records for which an explicit competing program beats the constructor’s returned program by more than that margin.

Standard numerical K remains enormously convenient. Mutual algorithmic information, structure functions, normalized information distances, and many compact AIT identities are most naturally written with numerical complexities. The claim is not that all of AIT survives unchanged if we throw away K. The more modest and, I think, more important claim is that the operational core of compression and model improvement need not take exact numerical K as primitive.

Reverse mathematics tells the same story from another side

Reverse mathematics asks how much formal strength is needed to prove familiar mathematical claims. Work by André Nies and Paul Shafer shows that substantial parts of algorithmic randomness and Kolmogorov-complexity reasoning can be carried out in the weak base theory RCA₀. This literature forces a distinction that ordinary textbook notation tends to hide: expressing and manipulating complexity comparisons is not the same thing as assuming the existence of a global noncomputable function as a set-like mathematical object.

That distinction fits the observer viewpoint beautifully. A finite scientist may possess particular programs, proofs, inequalities, and improvements without possessing an oracle that returns K(x) for arbitrary data. The useful mathematics concerns what can be certified locally and relationally.

Chaitin: proof has a horizon too

Chaitin’s incompleteness results bring Gödel back into AIT. Fix a sound, effectively axiomatized formal theory F and a reference universal machine U. There is a theory- and machine-dependent ceiling beyond which F cannot prove arbitrarily strong specific lower bounds of the form “K(x) is greater than n.”

Again the relativity matters. Change the theory, and the ceiling changes. A stronger formal system may settle a particular case that the weaker one could not. Chaitin does not show that a specific finite string is absolutely beyond every possible mathematical route to knowledge. The result says that no one fixed effective formal theory certifies arbitrarily far into the landscape of algorithmic incompressibility.

Truth may be plural without becoming subjective

This is where the pluralist-Platonist view becomes useful. There is a false dichotomy between “one absolute mathematical universe with one hidden truth value for every sentence” and “mathematics is merely a human invention.”

A realist can instead say: mathematical structures exist independently of us; statements have objective truth values within those structures; proofs reveal consequences of specified axioms; and there may be many equally legitimate structures rather than one all-encompassing intended universe.

On this picture, truth is not subjective. Whether a theorem holds in a given structure is not a matter of taste. But some unqualified questions — “is CH simply true?” — may be incomplete until one says which universe or conception of set is intended. Hamkins’s set-theoretic multiverse makes precisely this move, and Balaguer’s plenitudinous Platonism provides a broader metaphysical version of it. The Stanford Encyclopedia notes explicitly that Platonism need not commit one to determinate truth values for every independent set-theoretic proposition.

This also helps disentangle Gödel from mysticism. If G is independent of F, the formal fact is that F does not choose between G and its negation. A universist may insist that one of the resulting models captures the intended mathematical reality. A multiversist may take both worlds seriously. A constructivist may question whether either disjunct should be asserted without the relevant construction. The incompleteness theorem itself remains untouched.

What does this mean for physics?

Physics makes the stakes higher because mathematical models are supposed to describe a world we inhabit. A model may assign a quantity a value while no finite observer can derive, calculate, or measure it. Is that value nevertheless physically real?

There is no theorem that answers this question for us. Scientific realism, operationalism, structural realism, and related positions disagree about how model-assigned quantities connect to physical ontology. The cautious position for Kolmogorov Theory is therefore not to deny observer-independent reality, but to refuse to identify three different things:

Our formal results concern the middle line. They bound what finite procedures can construct or certify. That makes them compatible with a realist, constructivist, operationalist, or pluralist metaphysics.

Science does not need a certificate of final truth

There is a broader lesson here. Science rarely possesses globally optimal descriptions. It possesses models that beat previous models, explain more with less, transfer to new data, and survive attempts to replace them.

That is enough for progress.

If someone hands us a shorter program that reproduces the relevant data, we have learned something finite and objective: the old description was not optimal. If a new macroscopic model compresses and predicts across held-out realizations, we have acquired a better representation. Neither achievement requires access to the exact value of K(x), nor a proof that no future theory will ever do better.

This may be the most useful way to read Gödel, Turing, and AIT together. Gödel says no fixed effective formal system exhausts arithmetic consequence. Turing says no single terminating algorithm decides every computation. Chaitin says no fixed effective theory certifies arbitrarily deep algorithmic incompressibility. AIT then adds a constructive consolation: local finite witnesses still matter. A better program can be exhibited. A better theory can be tested. A shorter explanation can prove that the previous explanation was too long.

Truth without proof?

So does truth exist without proof?

There is no single answer forced on us by logic.

A classical realist can say yes: truth outruns every finite formal system. A constructivist can tie legitimate mathematical assertion more closely to proof or construction. A pluralist Platonist can affirm a mind-independent mathematical reality while denying that there is one uniquely privileged mathematical universe that assigns every sentence its absolute truth value.

What Gödel and Turing establish is narrower and more durable than any of these philosophies. No fixed effective procedure captures everything we can ask.

Algorithmic information theory inherits that limitation, but it also shows how to work productively inside it. We need not know the final value of K(x) to know that one description is shorter than another. We need not certify that our current model is globally optimal to establish that it improves on what came before. We need not settle the metaphysics of inaccessible truth in order to build a science of finite descriptions, finite witnesses, and finite observers.

For a finite observer, progress does not require possession of truth in full. It requires reliable ways of recognizing better descriptions when they appear.