Toward a generalized computability theory (Q1346903)

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.