An analogue-digital Church-Turing thesis

DOI10.1142/S0129054114400012MaRDI QIDQ2929623zbMATH OpenOpenAlexFDO

Authors José Félix Costa, Diogo Poças, John V. Tucker, Edwin Beggs

Publication date 14 November 2014

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054114400012

zbMATH Keywords

hybrid systemsanalog computationChurch-Turing thesisnon-uniform complexityanalog-digital systems

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 5064401
• Digital simulation of analog computation and Church's thesis
• scientific article; zbMATH DE number 6823178
• Reflections on the Church-Turing thesis
• Church's thesis and physical computation
• The promise of analog computation
• Analog computation beyond the Turing limit
• scientific article; zbMATH DE number 5064392
• New Computational Paradigms
• The Church-Turing thesis. A last vestige of a failed mathematical program

Cites work

• An optical model of computation
• Analog computation via neural networks
• Axiomatizing physical experiments as oracles to algorithms
• Computational complexity with experiments as oracles
• Computational complexity with experiments as oracles. II. Upper bounds
• Limits to measurement in experiments governed by algorithms
• On the Power of Threshold Measurements as Oracles
• On the computational power of dynamical systems and hybrid systems
• On the computational power of neural nets
• Oracles that measure thresholds: the Turing machine and the broken balance
• Physical oracles: the Turing machine and the Wheatstone bridge
• The impact of models of a physical oracle on computational power
• Unpredictability and undecidability in dynamical systems
• Why there is no such discipline as hypercomputation

Cited in

(8)

• A model of systems with modes and mode transitions
• A hierarchy for BPP//log\(\star\) based on counting calls to an oracle
• How much can analog and hybrid systems be proved (super-)Turing
• Digital simulation of analog computation and Church's thesis
• Machines that perform measurements
• scientific article; zbMATH DE number 5064401 (Why is no real title available?)
• The power of analogue-digital machines (extended abstract)
• The Power of Machines That Control Experiments

This page was built for publication: An analogue-digital Church-Turing thesis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2929623)