Physically-relativized Church–Turing Hypotheses: Physical foundations of computing and complexity theory of computational physics

2008/05/09 by Martin Ziegler · 24 citations
Computer Science · Mathematics · Physics and Astronomy · #Algorithm #Cellular Automata and Applications #Computability #Computability theory #Computability, Logic, AI Algorithms #Computation #Computer science #Epistemology #Evolutionary Algorithms and Applications #Kolmogorov complexity #Mathematics #Philosophy #Programming language #Structuralism (philosophy of science) #Super-recursive algorithm #Theoretical computer science #Time hierarchy theorem #Turing #Turing machine #Universal Turing machine #cs.CC #physics.comp-ph

paper · pdf · doi:10.1016/j.amc.2009.04.062

published in Applied Mathematics and Computation 215(4), 1431-1447 (Elsevier BV) · interdisciplinary paper: philosophy of physics, computational physics, computational complexity and computability

arxiv created 2008/05/09 · openalex publication_date 2009/05/05 · arxiv updated 2010/05/10 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05

Abstract

We turn `the' Church-Turing Hypothesis from an ambiguous source of sensational speculations into a (collection of) sound and well-defined scientific problem(s): Examining recent controversies, and causes for misunderstanding, concerning the state of the Church-Turing Hypothesis (CTH), suggests to study the CTH relative to an arbitrary but specific physical theory--rather than vaguely referring to ``nature'' in general. To this end we combine (and compare) physical structuralism with (models of computation in) complexity theory. The benefit of this formal framework is illustrated by reporting on some previous, and giving one new, example result(s) of computability and complexity in computational physics.

Citations

• On the definitions of computable real continuous functions
• Randomness and Complexity, From Leibniz to Chaitin
• An Axiomatic Basis for Quantum Mechanics
• Hypercomputation: computing more than the Turing machine
• Computational Power of Infinite Quantum Parallelism
• Ultimate physical limits to computation
• Unit disk graph recognition is NP-hard
• Relativizations of the P = ?NP Question
• The Existence of Noncollision Singularities in Newtonian Systems
• Effectively open real functions
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Transcending the Limits of Turing Computability
• Building Infinite Machines
• Computational universes
• On a class of O(n2) problems in computational geometry
• Conservative logic