Oracle: Difference between revisions
Jump to navigation
Jump to search
Added oracles list |
mNo edit summary |
||
| (2 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
{{Stub}} | |||
An oracle is a theoretical "black box" that can give an answer to any instance of a certain problem in a single operation. The problem can be of any complexity class. It can even be an undecidable problem such as the halting problem. | |||
== Turing machines == | |||
PAGE IN CONSTRUCTION | |||
== Types of oracles == | |||
* 0': decide the halting problem for computable programs. | * 0': decide the halting problem for computable programs. | ||
* 1': decide the halting problem for programs containing 0' | * 1': decide the halting problem for programs containing 0' | ||
* Ω': decide the halting problem of any program, including programs containing Ω' | * Ω': decide the halting problem of any program, including programs containing Ω'{{citation needed}} | ||
* Ω2': decide if a programs is well-founded (do not create any kind of paradox) | * Ω2': decide if a programs is well-founded (do not create any kind of paradox){{citation needed}} | ||
PAGE IN CONSTRUCTION | PAGE IN CONSTRUCTION | ||
Latest revision as of 03:44, 28 June 2026
An oracle is a theoretical "black box" that can give an answer to any instance of a certain problem in a single operation. The problem can be of any complexity class. It can even be an undecidable problem such as the halting problem.
Turing machines
PAGE IN CONSTRUCTION
Types of oracles
- 0': decide the halting problem for computable programs.
- 1': decide the halting problem for programs containing 0'
- Ω': decide the halting problem of any program, including programs containing Ω'[citation needed]
- Ω2': decide if a programs is well-founded (do not create any kind of paradox)[citation needed]
PAGE IN CONSTRUCTION