Can Newtonian systems, bounded in space, time, mass and energy compute all functions?

DOI10.1016/j.tcs.2006.10.010zbMath1108.68050OpenAlexW2052120697MaRDI QIDQ870250

J. V. Tucker, Edwin J. Beggs

Publication date: 12 March 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.10.010

zbMATH Keywords

computabilityhypercomputationexperimental computationNewtonian machines

Mathematics Subject Classification ID

Axiomatics, foundations (70A05)

Related Items

The physical Church thesis as an explanation of the Galileo thesis ⋮ The impact of models of a physical oracle on computational power ⋮ Physical oracles: the Turing machine and the Wheatstone bridge ⋮ On the Complexity of Measurement in Classical Physics ⋮ The Elliptic Integral Machine: A Collision-based Model of Computation ⋮ Computations with oracles that measure vanishing quantities ⋮ Programming Experimental Procedures for Newtonian Kinematic Machines ⋮ THE PHYSICAL CHURCH-TURING THESIS AND THE PRINCIPLES OF QUANTUM THEORY ⋮ Physical Computational Complexity and First-order Logic ⋮ Physical constraints on hypercomputation ⋮ Embedding infinitely parallel computation in Newtonian kinematics ⋮ Experimental computation of real numbers by Newtonian machines ⋮ Limits to measurement in experiments governed by algorithms ⋮ Computations via Newtonian and relativistic kinematic systems ⋮ Physically-relativized Church-Turing hypotheses: physical foundations of computing and complexity theory of computational physics ⋮ Computational complexity with experiments as oracles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computations via Newtonian and relativistic kinematic systems
• An architectonic for science. The structuralist program
• The wave equation with computable initial data such that its unique solution is not computable
• Undecidability and incompleteness in classical mechanics
• Concrete models of computation for topological algebras
• Computability and complexity of ray tracing
• Quantum algorithm for Hilbert's tenth problem
• Analog computers and recursive functions over the reals.
• Computable total functions on metric algebras, universal algebraic specifications and dynamical systems
• Embedding infinitely parallel computation in Newtonian kinematics
• Relativistic computers and the Turing barrier
• The many forms of hypercomputation
• Church's thesis meets the \(N\)-body problem
• Computational power of infinite quantum parallelism
• A Differentially Algebraic Replacement Theorem, and Analog Computability
• IS WAVE PROPAGATION COMPUTABLE OR CAN WAVE COMPUTERS BEAT THE TURING MACHINE?
• Classical physics and the Church--Turing Thesis
• A computable ordinary differential equation which possesses no computable solution
• Abstract Computability and Its Relation to the General Purpose Analog Computer (Some Connections Between Logic, Differential Equations and Analog Computers)
• Building Infinite Machines
• Unpredictability and undecidability in dynamical systems
• Coupled map lattices as computational systems
• The complexity of N-body simulation
• Computable and Continuous Partial Homomorphisms on Metric Partial Algebras
• Abstract versus concrete computation on metric partial algebras
• New Computational Paradigms
• Mathematical Theory of the Differential Analyzer