Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSpace-bounded Church-Turing thesis and computational tractability of closed systems
152
0
0.0
(
0
)
Added by
Cristobal Rojas
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic 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.
rate research
Read More
We describe the Turing Machine, list some of its many influences on the theory of computation and complexity of computations, and illustrate its importance.
We show that the time evolution of an open quantum system, described by a possibly time dependent Liouvillian, can be simulated by a unitary quantum circuit of a size scaling polynomially in the simulation time and the size of the system. An immediate consequence is that dissipative quantum computing is no more powerful than the unitary circuit model. Our result can be seen as a dissipative Church-Turing theorem, since it implies that under natural assumptions, such as weak coupling to an environment, the dynamics of an open quantum system can be simulated efficiently on a quantum computer. Formally, we introduce a Trotter decomposition for Liouvillian dynamics and give explicit error bounds. This constitutes a practical tool for numerical simulations, e.g., using matrix-product operators. We also demonstrate that most quantum states cannot be prepared efficiently.
We define the bounded jump of A by A^b = {x | Exists i <= x [phi_i (x) converges and Phi_x^[A|phi_i(x)](x) converges} and let A^[nb] denote the n-th bounded jump. We demonstrate several properties of the bounded jump, including that it is strictly increasing and order preserving on the bounded Turing (bT) degrees (also known as the weak truth-table degrees). We show that the bounded jump is related to the Ershov hierarchy. Indeed, for n > 1 we have X <=_[bT] 0^[nb] iff X is omega^n-c.e. iff X <=_1 0^[nb], extending the classical result that X <=_[bT] 0 iff X is omega-c.e. Finally, we prove that the analogue of Shoenfield inversion holds for the bounded jump on the bounded Turing degrees. That is, for every X such that 0^b <=_[bT] X <=_[bT] 0^[2b], there is a Y <=_[bT] 0^b such that Y^b =_[bT] X.
A Turmit is a Turing machine that works over a two-dimensional grid, that is, an agent that moves, reads and writes symbols over the cells of the grid. Its state is an arrow and, depending on the symbol that it reads, it turns to the left or to the right, switching the symbol at the same time. Several symbols are admitted, and the rule is specified by the turning sense that the machine has over each symbol. Turmites are a generalization of Langtons ant, and they present very complex and diverse behaviors. We prove that any Turmite, except for those whose rule does not depend on the symbol, can simulate any Turing Machine. We also prove the P-completeness of prediction their future behavior by explicitly giving a log-space reduction from the Topological Circuit Value Problem. A similar result was already established for Langtons ant; here we use a similar technique but prove a stronger notion of simulation, and for a more general family.
A graph separator is a subset of vertices of a graph whose removal divides the graph into small components. Computing small graph separators for various classes of graphs is an important computational task. In this paper, we present a polynomial time algorithm that uses $O(g^{1/2}n^{1/2}log n)$-space to find an $O(g^{1/2}n^{1/2})$-sized separator of a graph having $n$ vertices and embedded on a surface of genus $g$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
