Oracle: Difference between revisions
Jump to navigation
Jump to search
Added oracles list |
This page is under construction, but I haven't seen any sources myself with these oracles (is an oracle the same thing semantically as a subset of N?) |
||
| Line 3: | Line 3: | ||
* 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 | ||
Revision as of 21:15, 10 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 Ω'[citation needed]
- Ω2': decide if a programs is well-founded (do not create any kind of paradox)[citation needed]
PAGE IN CONSTRUCTION