A Relative Church-Turing-Deutsch Thesis from Special Relativity and Undecidability

• URL: http://arxiv.org/abs/2206.06419v1
• Date: Mon, 13 Jun 2022 18:58:41 GMT
• Title: A Relative Church-Turing-Deutsch Thesis from Special Relativity and Undecidability
• Authors: Blake Wilson, Ethan Dickey, Vaishnavi Iyer and Sabre Kais
• Abstract summary: We show that computing the time, space, or error accumulated by the global simulator are simulation properties and therefore are undecidable. These simulation properties give rise to special relativistic effects in the relative model which we use to construct a Church-Turing-Deutsch thesis.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Beginning with Turing's seminal work in 1950, artificial intelligence proposes that consciousness can be simulated by a Turing machine. This implies a potential theory of everything where the universe is a simulation on a computer, which begs the question of whether we can prove we exist in a simulation. In this work, we construct a relative model of computation where a computable \textit{local} machine is simulated by a \textit{global}, classical Turing machine. We show that the problem of the local machine computing \textbf{simulation properties} of its global simulator is undecidable in the same sense as the Halting problem. Then, we show that computing the time, space, or error accumulated by the global simulator are simulation properties and therefore are undecidable. These simulation properties give rise to special relativistic effects in the relative model which we use to construct a relative Church-Turing-Deutsch thesis where a global, classical Turing machine computes quantum mechanics for a local machine with the same constant-time local computational complexity as experienced in our universe.

Related papers

• Computational Dynamical Systems [0.6138671548064356]
  We give definitions for what it means for a smooth dynamical system to simulate a Turing machine. We show that 'chaotic' dynamical systems and 'integrable' dynamical systems cannot robustly simulate universal Turing machines. More broadly, our work elucidates what it means for one'machine' to simulate another, and emphasizes the necessity of defining low-complexity 'encoders' and 'decoders'
  arXiv  Detail & Related papers  (2024-09-18T17:51:48Z)
• DrEureka: Language Model Guided Sim-To-Real Transfer [64.14314476811806]
  Transferring policies learned in simulation to the real world is a promising strategy for acquiring robot skills at scale. In this paper, we investigate using Large Language Models (LLMs) to automate and accelerate sim-to-real design. Our approach is capable of solving novel robot tasks, such as quadruped balancing and walking atop a yoga ball.
  arXiv  Detail & Related papers  (2024-06-04T04:53:05Z)
• On the Representational Capacity of Recurrent Neural Language Models [56.19166912044362]
  We show that a rationally weighted RLM with computation time can simulate any deterministic probabilistic Turing machine (PTM) with rationally weighted transitions. We also provide a lower bound by showing that under the restriction to real-time computation, such models can simulate deterministic real-time rational PTMs.
  arXiv  Detail & Related papers  (2023-10-19T17:39:47Z)
• Towards Complex Dynamic Physics System Simulation with Graph Neural ODEs [75.7104463046767]
  This paper proposes a novel learning based simulation model that characterizes the varying spatial and temporal dependencies in particle systems. We empirically evaluate GNSTODE's simulation performance on two real-world particle systems, Gravity and Coulomb.
  arXiv  Detail & Related papers  (2023-05-21T03:51:03Z)
• Computing spacetime [0.0]
  We advocate a principle of spacetime complexity, where gravity arises as a consequence of spacetime optimizing the computational cost of its own quantum dynamics. We visualize spacetime complexity using Lorentzian threads which represent the operations needed to prepare a quantum state in a tensor network discretizing spacetime.
  arXiv  Detail & Related papers  (2022-05-11T18:00:10Z)
• Computational Hierarchy of Elementary Cellular Automata [0.0]
  We study the ability of cellular automata to emulate one another. We show that certain chaotic automata are the only ones that cannot emulate any automata non-trivially. We believe our work can help design parallel computational systems that are Turing-complete and also computationally efficient.
  arXiv  Detail & Related papers  (2021-08-01T10:00:54Z)
• Towards Cosmological Simulations of Dark Matter on Quantum Computers [0.0]
  Quantum computers can perform some calculations exponentially faster than classical computers. Quantum circuits act linearly on quantum states, so nonlinearities (e.g. self-gravity in cosmological simulations) pose a significant challenge. Here we outline one potential approach to overcome this challenge and solve the (nonlinear) Schrodinger-Poisson equations for the evolution of self-gravitating dark matter.
  arXiv  Detail & Related papers  (2021-01-14T19:00:06Z)
• Probability and consequences of living inside a computer simulation [77.65665055163332]
  It is shown that under reasonable assumptions a Drake-style equation can be obtained for the probability that our universe is the result of a deliberate simulation. We investigate the possibility of eavesdropping from the outside of such a simulation and introduce a general attack that can circumvent attempts at quantum cryptography inside the simulation.
  arXiv  Detail & Related papers  (2020-08-21T02:41:33Z)
• Reservoir memory machines [79.79659145328856]
  We propose reservoir memory machines, which are able to solve some of the benchmark tests for Neural Turing Machines. Our model can also be seen as an extension of echo state networks with an external memory, enabling arbitrarily long storage without interference.
  arXiv  Detail & Related papers  (2020-02-12T01:45:00Z)
• Simulation of Thermal Relaxation in Spin Chemistry Systems on a Quantum Computer Using Inherent Qubit Decoherence [53.20999552522241]
  We seek to take advantage of qubit decoherence as a resource in simulating the behavior of real world quantum systems. We present three methods for implementing the thermal relaxation. We find excellent agreement between our results, experimental data, and the theoretical prediction.
  arXiv  Detail & Related papers  (2020-01-03T11:48:11Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.