Computation and Physics

          @misc{ pirsa_PIRSA:08030001,
            doi = {10.48660/08030001},
            url = {https://pirsa.org/08030001},
            author = {Geroch, Robert},
            keywords = {Quantum Gravity},
            language = {en},
            title = {Computation and Physics},
            publisher = {Perimeter Institute},
            year = {2008},
            month = {mar},
            note = {PIRSA:08030001 see, \url{https://pirsa.org}}
          }
          

Abstract

There are two notions that play a central role in the mathematical theory of computation. One is that of a computable problem, i.e., of a problem that can, in principle, be solved by an (idealized) computer. It is known that there exist problems that \'have answers\', but for which those answers are not computable. The other is that of the difficulty of a computation, i.e. of the number of (idealized) steps required actually to carry out that computation. It is known that, given any appropriate \'degree of difficulty\', there exists a problem that, while computable, is at least that difficult. These two notions, while purely mathematical, are designed to reflect, in some broad sense, the physics of the computation process. But there are indications that physics may have something further to say about them. Indeed, it has been suggested that, by using general relativity, some problems that are (mathematically) non-computable may become computable; and that, by using quantum mechanics, some problems that are (mathematically) difficult may become less so. Are there, in principle, any limitations on what physics can do for us in this area?