A Relative Church-Turing-Deutsch Thesis from Special Relativity and Undecidability
This addresses foundational questions in AI and physics about simulation and computability, but it is incremental as it builds on existing undecidability and relativity concepts.
The paper tackles the problem of whether a simulated entity can determine properties of its simulator, showing that computing simulation properties like time, space, or error is undecidable, akin to the Halting problem. It results in a relative Church-Turing-Deutsch thesis where a global Turing machine computes quantum mechanics for a local machine with constant-time complexity matching our universe.
Beginning with Turing's seminal work in 1950, artificial intelligence proposes that consciousness can be simulated by a Turing machine. This implies a potential theory of everything where the universe is a simulation on a computer, which begs the question of whether we can prove we exist in a simulation. In this work, we construct a relative model of computation where a computable \textit{local} machine is simulated by a \textit{global}, classical Turing machine. We show that the problem of the local machine computing \textbf{simulation properties} of its global simulator is undecidable in the same sense as the Halting problem. Then, we show that computing the time, space, or error accumulated by the global simulator are simulation properties and therefore are undecidable. These simulation properties give rise to special relativistic effects in the relative model which we use to construct a relative Church-Turing-Deutsch thesis where a global, classical Turing machine computes quantum mechanics for a local machine with the same constant-time local computational complexity as experienced in our universe.