The Church-Turing Thesis and Physics

Abstract:

Even as quantum computing challenges the polynomial-time Church-Turing Thesis, the original, computability-theoretic Church-Turing Thesis has seemed to be on remarkably solid ground. In this talk I’ll survey the status of the Church-Turing Thesis in 2017, interpreting it as a falsifiable empirical claim about what’s computable in the physical world. I’ll touch on energy limits to computation, the Bekenstein bound, and the AdS/CFT correspondence in quantum gravity, and the controversial speculations of Roger Penrose. I’ll then explain a recent result by myself, Mohammad Bavarian, and Giulio Gueltrini, which shows that in a world with closed timelike curves (CTCs), the halting problem would become solvable with finite resources, although in some sense not much “more” than the halting problem (the limit is either the problems Turing reducible or those weakly truth-table reducible to the halting problem, depending on one’s model for CTCs). One can, of course, interpret this result as additional evidence against the possibility of CTCs in our universe.