Oracle: Difference between revisions
Jump to navigation
Jump to search
Created the page |
Added oracles list |
||
| Line 1: | Line 1: | ||
An oracle is a 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, or it can even be an undecidable problem such as the halting problem. | An oracle is a 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, or it can even be an undecidable problem such as the halting problem. | ||
* 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 Ω' | |||
* Ω2': decide if a programs is well-founded (do not create any kind of paradox) | |||
PAGE IN CONSTRUCTION | |||
Revision as of 18:44, 9 June 2026
An oracle is a 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, or it can even be an undecidable problem such as the halting problem.
- 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 Ω'
- Ω2': decide if a programs is well-founded (do not create any kind of paradox)
PAGE IN CONSTRUCTION