Computations with oracles
type: Item
instance of: scholarly article
title: Computations with oracles
zbMATH Open document ID: 0582.03020
DOI: 10.1007/BF00968804
author: N. A. Plotnikova
published in: Siberian Mathematical Journal
publication date: 1983-01-01T00:00:00Z
review text: We investigate a class of generalized calculations on Turing machines with oracles which were considered in papers by \textit{N. V. Belyakin} [Mat. Sb., Nov. Ser. 101(143), 21-43 (1976; Zbl 0342.02031)] and \textit{V. A. Ganov} [''The selector function and the continuum hypothesis'' (Russian) (manuscript deposited at VINITI (Moscow) No.94-81)]. We use as oracles one-place functions not everywhere defined which satisfy the special conditions of regularity, weak groundedness and normalizability. In Section 1 we show that the idea of enumerability of sets with oracles can be substantially strengthened. In Section 2 we introduce the condition of decomposability of an oracle and prove its equivalence to the condition of normalizability.
Mathematics Subject Classification ID: 03D10
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 3930981
zbMATH Keywords: generalized calculations
zbMATH Keywords: Turing machines with oracles
zbMATH Keywords: one-place functions
zbMATH Keywords: normalizability
zbMATH Keywords: decomposability of an oracle
MaRDI profile type: Publication
cites work: Q4109663
cites work: Q5573961
full work available at URL: https://doi.org/10.1007/bf00968804
OpenAlex ID: W2058217188
description: scientific article; zbMATH DE number 3930981