2015/08/27 by Mark Braverman, Cristobal Rojas, Cristóbal Rojas +1
Computer Science · Mathematics · #Algorithm #Assertion #Bounded function #Cellular Automata and Applications #Computability, Logic, AI Algorithms #Computation #Computer science #Corollary #DTIME #Discrete mathematics #Mathematics #Quantum Computing Algorithms and Architecture #Space (punctuation) #Super-recursive algorithm #Theoretical computer science #Turing machine #Universal Turing machine #Upper and lower bounds #cs.CC #msc:37C40 #msc:68Q05
paper · pdf · doi:10.1103/physrevlett.115.098701
published as Physical Review Letters. 115, 098701. August 2015 · 6 pages
openalex publication_date 2015/08/27 · arxiv created 2019/05/02 · arxiv updated 2019/05/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
We report a new limitation on the ability of physical systems to perform computation-one that is based on generalizing the notion of memory, or storage space, available to the system to perform the computation. Roughly, we define memory as the maximal amount of information that the evolving system can carry from one instant to the next. We show that memory is a limiting factor in computation even in lieu of any time limitations on the evolving system-such as when considering its equilibrium regime. We call this limitation the space-bounded Church-Turing thesis (SBCT). The SBCT is supported by a simulation assertion (SA), which states that predicting the long-term behavior of bounded-memory systems is computationally tractable. In particular, one corollary of SA is an explicit bound on the computational hardness of the long-term behavior of a discrete-time finite-dimensional dynamical system that is affected by noise. We prove such a bound explicitly.