Generalized computations with binary oracles
type: Item
instance of: scholarly article
title: Generalized computations with binary oracles
zbMATH Open document ID: 0852.03014
DOI: 10.1007/BF02261706
author: R. V. Ganova
published in: Algebra and Logic
publication date: 1995-04-20T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 03D10
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 738959
zbMATH Keywords: Turing machines with binary oracles
zbMATH Keywords: hyperarithmetic computability
reviewed by: Lei Qian
MaRDI profile type: Publication
cites work: Q4087153
cites work: Q4109663
cites work: Q4303550
cites work: Q5573961
full work available at URL: https://doi.org/10.1007/bf02261706
OpenAlex ID: W2069474428
description: scientific article; zbMATH DE number 738959