An external approach to abstract data types I: computability on abstract data type

Abstract

A characterization of the effective abstract data types from the recursion theoretical point of view is presented. The main tool is a notion of compatibility on many-sorted abstract structures. This notion has certain maximal properties under natural conditions.

The relationships between certain special properties of the class of the computable functions is an abstract structure and the existence of some special enumerations of it are considered.