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.
scientific article; zbMATH DE number 738959