RECORD
Space-bounded Church-Turing thesis and computational tractability of closed systems
Computational Complexity · Submitted 2 May 2019
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim 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.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | 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. | contribution 0.88 | 0.90 | 0.61 | asserted 1.00 |
| s1 | Roughly, we define memory as the maximal amount of information that the evolving system can carry from one instant to the next. | method 0.51 | 0.53 | 0.04 | asserted 0.83 |
| s2 | 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. | result 0.95 | 0.88 | 0.42 | asserted 1.00 |
| s3 | We call this limitation the Space-Bounded Church Turing Thesis (SBCT). | contribution 0.83 | 0.73 | 0.22 | asserted 0.91 |
| s4 | The SBCT is supported by a Simulation Assertion (SA), which states that predicting the long-term behavior of bounded-memory systems is computationally tractable. | contribution 0.64 | 0.56 | 0.24 | asserted 0.99 |
| s5 | 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. | result 0.68 | 0.70 | 0.14 | asserted 0.99 |
| s6 | We prove such a bound explicitly. | contribution 0.56 | 0.95 | 0.10 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
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.
Human review
How the literature uses it
What this paper does with the arXiv papers it cites
What it cites · 2 sentences without a confident label
Cites as support 2 papers
-
For instance, there exist computable dynamical systems (e.g. maps on the unit interval [ref] or cellular automata [ref] ) for which there is a positive measure set of initial conditions leading to the same equilibrium regime — so it is a “physical state” — that yet no Turing machine can simulate in this way.
Dynamics and abstract computability: computing invariant measures · Introduction · 0.99
-
For instance, there exist computable dynamical systems (e.g. maps on the unit interval [ref] or cellular automata [ref] ) for which there is a positive measure set of initial conditions leading to the same equilibrium regime — so it is a “physical state” — that yet no Turing machine can simulate in this way.
Characterisation of sets of limit measures after iteration of a cellular automaton on an initial measure · Introduction · 0.99
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.