The Physicality of Logic: On the Refutation of Incompleteness, Undecidability, and Computational Complexity Gaps as Features of Physical Reality

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 when every problem instance is bounded by the information capacity of the finite physical substrate. The Travelling Salesman Problem is developed as a concrete application of the finite-domain argument. Every physically instantiable TSP instance has a bounded number of cities, a finite number of routes, and is therefore decidable by exhaustive enumeration — trivially in P by table lookup, as the complexity literature itself acknowledges for fixed-size instances. Its practical difficulty for large instances is not a consequence of NP-completeness but a physical resource constraint: the construction of the optimal route requires more causal steps in the preonic dynamics than are available within the constraints of the physical substrate and the time allocated. The P vs NP distinction, defined over infinite asymptotic families, is the wrong framework for characterising this difficulty. Physical constructivism provides the correct one. 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. As a further application, the paper develops a physical constructivist restatement of Fermat's Last Theorem. The theorem reduces, under the four principles, 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. 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 empirical and theoretical, 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" and to the book Quantum-Geometry Dynamics: An Axiomatic Approach to Physics.