Generalized computations with binary oracles
The author discusses a special kind of Turing machines with oracles -- Turing machines with binary oracles. Usually, an oracle used by a machine is unary. That means we can consider it as a unary function. But the oracles used in the model of this paper are binary functions with certain consistent restrictions. Such machines can be used for modeling hyperarithmetic computability iterated to the first constructive inaccessible ordinal. Usually, a binary oracle is not total. If a computation asks an oracle a question and the answer is undefined, then we have several methods to treat it. In some models, we treat it as an answer of a special kind; in some other models, we come to a deadlock. In this paper, the author considers properties of a model which interprets the first \(n\) such answers as special kind answers and the \(n+1\)st answer as deadlock.
- Computations with oracles
- Complete divisibility problems for slowly utilized oracles
- Generic oracles, uniform machines, and codes
- A tight relationship between generic oracles and type-2 complexity theory
- On a certain nontraditional version of computations with oracles
- Computability with two-place oracle
- Computations with oracles: Generalized selection
- scientific article; zbMATH DE number 4005621 (Why is no real title available?)
- scientific article; zbMATH DE number 1354009 (Why is no real title available?)
- scientific article; zbMATH DE number 2047480 (Why is no real title available?)
- scientific article; zbMATH DE number 2047497 (Why is no real title available?)
- Modeling hyperarithmetic computability on machines with constraints
- Oracle programming in a higher level language
- Oracle programming in a higher level language
This page was built for publication: Generalized computations with binary oracles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1346911)
