The Power of Machines That Control Experiments

DOI10.1142/S0129054122500010MaRDI QIDQ6114859zbMATH OpenOpenAlexFDO

Authors José Félix Costa, Diogo Poças

Publication date 15 August 2023

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

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

zbMATH Keywords

analog computationanalog-digital systemsChurch-Turing thesishybrid systemsnon-uniform complexity

Mathematics Subject Classification ID

Classical models of computation (Turing machines, etc.) (68Q04) Other nonclassical models of computation (68Q09) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Computational complexity with experiments as oracles
• Computational complexity with experiments as oracles. II. Upper bounds
• Limits to measurement in experiments governed by algorithms
• Three forms of physical measurement and their computability
• Physical oracles: the Turing machine and the Wheatstone bridge

Cites work

• A hierarchy for BPP//log\(\star\) based on counting calls to an oracle
• An analogue-digital Church-Turing thesis
• 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
• Computations with oracles that measure vanishing quantities
• scientific article; zbMATH DE number 44307 (Why is no real title available?)
• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• scientific article; zbMATH DE number 1260390 (Why is no real title available?)
• scientific article; zbMATH DE number 3314823 (Why is no real title available?)
• Limits to measurement in experiments governed by algorithms
• On the computational power of neural nets
• On the Power of Threshold Measurements as Oracles
• 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
• Three forms of physical measurement and their computability
• Why there is no such discipline as hypercomputation

Cited in

(4)

• Machines that perform measurements
• On the Complexity of Measurement in Classical Physics
• Computational complexity with experiments as oracles. II. Upper bounds
• Computational complexity with experiments as oracles

This page was built for publication: The Power of Machines That Control Experiments

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