Toward a generalized computability theory

DOI10.1007/BF02261744MaRDI QIDQ1346903zbMATH OpenFDO

Authors I. V. Ashaev, V. Ya. Belyaev, Alexei Myasnikov

Publication date 20 April 1995

Published in Algebra and Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF02261744

algebraic systems algorithm BSS-machines list extension recursive functions

Turing machines and related notions (03D10) Recursive functions and relations, subrecursive hierarchies (03D20) Recursively (computably) enumerable sets and degrees (03D25)

Review text

The main objective of the paper is to extend the classical notion of an algorithm to arbitrary algebraic systems. Algorithmic constructions are chosen as in well-known standard program schemes, and are called BSS- machines following the names of \textit{L. Blum}, \textit{M. Shub}, and \textit{S. Smale} being the authors of the paper: ``On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines [Bull. Am. Math. Soc., New Ser. 21, No. 1, 1-46 (1989; Zbl 0681.03020)]. The basic idea of the suggested approach is to use BSS-machines over the list extension of a system \({\mathfrak A}\) and not over \({\mathfrak A}\) itself. Different generalizations of classical recursive functions in the theory of algorithms are introduced and studied from this point of view.

Recommendations

Cites work

Cited in

(22)

This page was built for publication: Toward a generalized computability theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1346903)