Physically-relativized Church-Turing hypotheses: physical foundations of computing and complexity theory of computational physics
From MaRDI portal
Publication:1036536
DOI10.1016/j.amc.2009.04.062zbMath1192.68268OpenAlexW1619090842MaRDI QIDQ1036536
Publication date: 13 November 2009
Published in: Applied Mathematics and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.amc.2009.04.062
Related Items
The physical Church thesis as an explanation of the Galileo thesis, The impact of models of a physical oracle on computational power, On Computability of Navier-Stokes’ Equation, Physical oracles: the Turing machine and the Wheatstone bridge, Computations with oracles that measure vanishing quantities, Unconventional algorithms: complementarity of axiomatics and construction, THE PHYSICAL CHURCH-TURING THESIS AND THE PRINCIPLES OF QUANTUM THEORY, Limits to measurement in experiments governed by algorithms, Computable analysis with applications to dynamic systems, Computations via Newtonian and relativistic kinematic systems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- ``Linear chaos via paradoxical set decompositions.
- Effectively open real functions
- Computing Schrödinger propagators on type-2 Turing machines
- Can Newtonian systems, bounded in space, time, mass and energy compute all functions?
- Computations via Newtonian and relativistic kinematic systems
- The computational complexity of maximization and integration
- Church's thesis and the ideal of informal rigour
- The wave equation with computable initial data such that its unique solution is not computable
- Conservative logic
- The existence of noncollision singularities in Newtonian systems
- A formal background to mathematics. Ia, Ib: Logic, sets and numbers
- A survey on real structural complexity theory
- Computability and complexity of ray tracing
- Unit disk graph recognition is NP-hard
- Quantum algorithm for Hilbert's tenth problem
- Constructive mathematics and quantum physics
- Universal computation and physical dynamics
- On a class of \(O(n^ 2)\) problems in computational geometry
- Computational universes
- Embedding infinitely parallel computation in Newtonian kinematics
- The Church-Turing thesis: Still valid after all these years?
- Church's thesis meets the \(N\)-body problem
- Three counterexamples refuting Kieu's plan for ``quantum adiabatic hypercomputation; and some uncomputable quantum mechanical tasks
- Computational power of infinite quantum parallelism
- A theory of computation based on quantum logic. I
- Division in logspace-uniformNC1
- IS WAVE PROPAGATION COMPUTABLE OR CAN WAVE COMPUTERS BEAT THE TURING MACHINE?
- On the definitions of computable real continuous functions
- SHORTEST PATH AMIDST DISC OBSTACLES IS COMPUTABLE
- Classical physics and the Church--Turing Thesis
- Log Depth Circuits for Division and Related Problems
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- P-COMPLETE GEOMETRIC PROBLEMS
- On the Power of Real Turing Machines over Binary Inputs
- Mathematical Constructivism in Spacetime
- Unpredictability and undecidability in dynamical systems
- A Constructivist Perspective on Physics
- The complexity of N-body simulation
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- Binary black holes on a budget: simulations using workstations
- Wave function of the Universe
- Experimental computation of real numbers by Newtonian machines
- Computational complexity with experiments as oracles
- Classical Mechanics as a Limit of Quantum Mechanics
- Quantum logic as motivated by quantum computing
- On Computable Numbers, with an Application to the Entscheidungsproblem
- Logical Approaches to Computational Barriers
- The logical structure of mathematical physics
- Non-Turing computations via Malament--Hogarth space-times
