Computation Is Bound by Physical Laws: A Fact-Based Church-Turing Thesis

- The **Church-Turing thesis** (orig. 1930s) says any function computable by an algorithm can be computed by a Turing machine. The **Physical Church-Turing thesis** extends this: any computation realizable in the physical universe can be simulated by a Turing machine. The article argues this is an empirical fact about physics, not just a mathematical assumption. - **Quantum computing** is often cited as a challenge: quantum algorithms can solve certain problems (e.g. integer factorization via Shor's algorithm) exponentially faster than any known classical method. Some researchers claim this violates the Physical Church-Turing thesis — that nature "computes" things a Turing machine fundamentally cannot. - The article counters that quantum computers do not expand the set of computable problems; they merely offer speedups within the same physical laws. The dispute is active in theoretical CS and physics, with stakes for AI limits, cryptography security, and the nature of physical reality.