Deterministic and nondeterministic computation, and horn programs, on abstract data types

AbstractWe investigate the notion of “semicomputability,” intended to generalize the notion of recursive enumerability of relations to abstract structures. Two characterizations are considered and shown to be equivalent: one in terms of “partial computable functions” (for a suitable notion of computability over abstract structures) and one in terms of definability by means of Horn programs over such structures. This leads to the formulation of a “Generalized Church-Turing Thesis” for definability of relations on abstract structures