The Physical Church-Turing Thesis: Computation as a Fundamental Physical Process

We propose a fundamental revision of the Church-Turing thesis that recognizes computation as an inherently physical process constrained by the laws of thermodynamics, quantum mechanics, and relativity. The classical Church-Turing thesis states that any effectively calculable function can be computed by a Turing machine, but this formulation ignores the physical substrate required for computation. We establish the Physical Church-Turing Thesis: any effectively calculable function that can be physically computed must respect the fundamental constraints imposed by physical law. We develop a rigorous framework based on erasure complexity and reversible computation that leads to provable energy lower bounds for computational problems. Our analysis shows that physical computability can form a proper subset of Turing computability under explicit resource constraints, as formalized by our erasure-based framework. We provide concrete theorems connecting time-space-coherence trade-offs to unavoidable bit erasures, yielding quantitative energy bounds via Landauer's principle. The framework unifies computation theory with fundamental physics and provides practical guidance for energy-efficient algorithm design.