Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Oracle machine
open-in-new
<p>In <a href="/facts/Computational_complexity_theory/etHuVF3U">complexity theory</a> and <a href="/facts/Computability_theory/cqDfXwdf">computability theory</a>, an oracle machine is an <a href="/facts/Abstract_machine/zuC4RKLn">abstract machine</a> used to study <a href="/facts/Decision_problem/cQNWjbdE">decision problems</a>. It can be visualized as a <a href="/facts/Black_box/hJeAGnIz">black box</a>, called an oracle, which is able to solve certain problems in a single operation. The problem can be of any <a href="/facts/Complexity_class/IIKrcTbP">complexity class</a>. Even <a href="/facts/Undecidable_problem/QBxmXBbY">undecidable problems</a>, such as the <a href="/facts/Halting_problem/Xz1bac40">halting problem</a>, can be used. </p>