oracle machine

English

Noun

oracle machine (plural oracle machines)

1. (computing theory) In computability theory, a form of theoretical Turing machine, able to solve even undecidable decision problems in a single operation.
   • 1994, Roger Penrose, “Quantum theory and the brain”, in Shadows of the Mind, Oxford University Press, →ISBN, page 380:

     Thus, an oracle machine (which enacts an oracle algorithm) would be like an ordinary Turing machine, except that adjoined to its ordinary computational operations would be another operation: ‘Call in the oracle and ask it whether C_q(n) stops; […]

Translations

theoretical machine

Chinese: Mandarin: 預言機 / 预言机 (yùyánjī) Finnish: oraakkelikone (fi) French: please add this translation if you can

Further reading

• oracle machine on Wikipedia.Wikipedia