Oracle: Difference between revisions
Jump to navigation
Jump to search
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?) |
mNo edit summary |
||
| (One intermediate revision by one other user 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' | ||
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