The Physicality of Logic: On the Refutation of Incompleteness, Undecidability, and Computational Complexity Gaps as Features of Physical Reality
Daniel Burnstein · Zenodo (CERN European Organization for Nuclear Research) · 2026
Three foundational results of twentieth-century mathematical logic — Gödel's incompleteness theorems, Turing's undecidability of the halting problem, and the P vs NP complexity gap — have been widely taken to impose permanent limitations on what a physical theory can achieve. This paper argues that all three applications rest on the same category error: the attribution to physical reality of properties that belong only to formal systems operating over infinite domains. Under the framework of Minimal Physically Derivable Theories (MPDT), established by the Uniqueness Theorem, physical reality is constituted by a finite discrete substrate whose total information capacity is bounded. A formal system whose intended domain is this finite substrate does not satisfy the preconditions of any of the three results. Gödel's theorems require arithmetical sufficiency over an infinite model — a condition no finite physical domain satisfies. Turing's undecidability proof requires an infinite tape — the halting problem is provably decidable for any finite-state machine, and every physical computer is a finite-state machine. The P vs NP distinction requires asymptotic growth over unbounded input sizes — a distinction that collapses in a finite domain where every problem instance has a bounded maximum size. The paper then develops the positive account that the MPDT framework requires: physical constructivism, grounded in four principles. First, a mathematical object does not exist until its construction has been physically completed — prior to completion, it does not exist. Second, mathematical notation is a prescription for a construction, not a name for a pre-existing object: the expression xⁿ is an instruction to multiply, not a number; √2 is an instruction to find a root, not a number. Third, irrational numbers are prescriptions whose constructions never complete within finite resources and therefore do not exist as physical objects. Fourth, every physical computation terminates — either by completing its construction or by exhausting physical resources — there are no infinite processes in a finite physical universe. Under physical constructivism, the classical category of undecidable propositions — true but unprovable — does not exist within the physical theory, because truth and physical constructibility are co-extensive. The classical triad of true, false, and undecidable collapses to a binary: constructible or physically unrepresentable. As a concrete application, the paper develops a physical constructivist restatement of Fermat's Last Theorem. Under the four principles, the theorem reduces to the claim that the construction mode C(x, y, n) = (xⁿ + yⁿ)^(1/n) never produces a constructed integer for positive integer inputs x, y and exponent n greater than 2. The rational root theorem eliminates rational non-integer outputs; the resource exhaustion principle and the irrationality principle together eliminate irrational outputs. The construction either produces an integer or produces nothing. Fermat's Last Theorem is therefore, under physical constructivism, a decidable claim about the termination behaviour of a specific physical construction mode operating over a finite domain — not a claim about the non-existence of objects in an infinite mathematical domain requiring the deep machinery of Wiles's proof. The paper concludes that Hilbert's sixth problem — the axiomatisation of physics — is not blocked by any of the three classical results. The challenge of identifying the correct minimal axiom set remains an empirical and theoretical one, not a logical impossibility. In a minimal physical universe, to exist is to be constructible, and to be constructible is to be the completed output of a physical process that terminated before resources ran out. The paper is intended for philosophers of physics, philosophers of mathematics, mathematical logicians, and theoretical physicists working on foundational questions. It is a companion to the author's paper "On the Uniqueness of Minimal Physically Derivable Theories," also available on Zenodo, and to the book Quantum-Geometry Dynamics: An Axiomatic Approach to Physics (2026).