Computational complexity with experiments as oracles | Zendy

Edwin Beggs | Zendy; José Félix Costa | Zendy; Bruno Loff | Zendy; John V. Tucker | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Computational complexity with experiments as oracles

Author(s) -

Edwin Beggs,

José Félix Costa,

Bruno Loff,

John V. Tucker

Publication year - 2008

Publication title -

proceedings of the royal society a mathematical physical and engineering sciences

Language(s) - English

Resource type - Journals

eISSN - 1471-2946

pISSN - 1364-5021

DOI - 10.1098/rspa.2008.0085

Subject(s) - turing machine , universal turing machine , computer science , description number , super recursive algorithm , class (philosophy) , turing , set (abstract data type) , turing machine examples , theoretical computer science , computation , algorithm , artificial intelligence , programming language

We discuss combining physical experiments with machine computations and intro- duce a form of analogue-digital Turing machine. We examine in detail a case study where an experimental procedure based on Newtonian kinematics is combined with a class of Turing machines. Three forms of analogue-digital machine are studied, in which physical parameters can be set exactly and approximately. Using non-uniform com- plexity theory, and some probability, we prove theorems that show that these machines can compute more than classical Turing machines.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research