Equivalence of two models of computations in algebraic structures
Equivalence of two models of computations in algebraic structures
(Russian, English abstract)
Siberian Electronic Mathematical Reports, 23, 2, pp. 766-778 (2026)
Abstract:
In this paper, we study two models of computability over an arbitrary algebraic structure:
list-superstructure computability by Ashaev, Belyaev and Myasnikov, and computability of Moschovakis. We prove equivalence of these models for the classes of primitive computable functions. Also we expand the notion of partial computable function in the list-superstructure computability to prove its equivalence to the notion of computable function in the Moschovakis model.
Keywords: generalized computability, list-superstructure, Moschovakis model.
