I will give this talk on 10 September at the “First International Conference on Logic and Relativity: honoring István Németi’s 70th birthday” at the Alfréd Rényi Institute of Mathematics in Budapest.
Here is an abstract:
There exists a growing literature on the so-called physical Church-Turing thesis in a relativistic spacetime setting. The physical Church-Turing thesis is the conjecture that no computing device that is physically realizable (even in principle) can exceed the computational barriers of a Turing machine. By suggesting a concrete implementation of a beyond-Turing computer in a spacetime setting, Istv\’an Nem\’eti and his collaborators G\abor Etesi and Gyula D\’avid have shown how an appreciation of the physical Church-Turing thesis necessitates the confluence of mathematical, computational, physical, and indeed cosmological ideas. In this talk, I will honour Istv\’an’s seventieth birthday, as well as his longstanding interest in, and his seminal contributions to, this field going back to as early as 1987 by offering a prolegomenon to how the concrete implementation in proposed by Nem\’eti and collaborators may or may not be complemented by a quantum-information-theoretic communication protocol between the computing device and the logician who sets the beyond-Turing computer a task such as determining the consistency of Zermelo-Fraenkel set theory. This suggests that even the foundations of quantum theory and, ultimately, quantum gravity may play an important role in determining the validity of the physical Church-Turing thesis.