Equivalence of two models of computations in algebraic structures

Equivalence of two models of computations in algebraic structures

(Russian, English abstract)

Karatsev N. R., Rybalov A. N.
Siberian Electronic Mathematical Reports, 23, 2, pp. 766-778 (2026)

УДК 510.652 
DOI: 10.33048/semi.2026.23.049  
MSC 11U99


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.