Difference between revisions of "Oracle"
Jump to navigation
Jump to search
| Line 1: | Line 1: | ||
In [[mathematics]], an [[oracle]] is a black box posited in [[logic]] which, without revealing the methods of [[proof]], can decide whether a statement is [[true]] or [[false]]. In higher [[computability]] theory, one often makes use of oracles that can solve the [[Halting problem]] to deduce the [[undecidable|undecidability]] of [[computing]] problems. | In [[mathematics]], an [[oracle]] is a black box posited in [[logic]] which, without revealing the methods of [[proof]], can decide whether a statement is [[true]] or [[false]]. In higher [[computability]] theory, one often makes use of oracles that can solve the [[Halting problem]] to deduce the [[undecidable|undecidability]] of [[computing]] problems. | ||
| − | The term ''oracle'' is taken from the Greek [[Oracle at Delphi]], a pagan | + | The term ''oracle'' is taken from the Greek [[Oracle at Delphi]], a pagan priestess, who, when drugged appropriately, could see the future. The oracle is a central part of many Greek myths, and is often used to teach the lesson that "no man can escape his fate" (see also [[hubris]]). |
[[category:logic]][[category:mathematics]] | [[category:logic]][[category:mathematics]] | ||
Revision as of 22:24, February 27, 2009
In mathematics, an oracle is a black box posited in logic which, without revealing the methods of proof, can decide whether a statement is true or false. In higher computability theory, one often makes use of oracles that can solve the Halting problem to deduce the undecidability of computing problems.
The term oracle is taken from the Greek Oracle at Delphi, a pagan priestess, who, when drugged appropriately, could see the future. The oracle is a central part of many Greek myths, and is often used to teach the lesson that "no man can escape his fate" (see also hubris).