×

Generalized computations with binary oracles. (English. Russian original) Zbl 0852.03014

Algebra Logic 32, No. 5, 257-266 (1993); translation from Algebra Logika 32, No. 5, No. 5, 479-496 (1993).
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.
Reviewer: Qian Lei (Nanjing)

MSC:

03D10 Turing machines and related notions
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] L. N. Pobedin, ”Certain questions on general computability,”Algebra Logika, 12, No. 2, 220–231 (1973).
[2] L. N. Pobedin, ”Halting problem and hierarchy theory,”Algebra Logika, 14, No. 2, 186–203 (1975). · Zbl 0324.02024
[3] N. V. Belyakin, ”Iterated Kleene computability and superjump,”Mat. Sb., 101, No. 1, 21–43 (1976). · Zbl 0342.02031
[4] V. A. Ganov and N. V. Belyakin,General Theory of Computations with Oracles, Institute of Mathematics, Novosibirsk (1989). · Zbl 0797.03041
[5] H. Rogers,Theory of Recursive Functions and Effective Computability, McGraw-Hill (1967). · Zbl 0183.01401
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.