Computability of String Functions Over Algebraic Structures (Preliminary Version)

We present a model of computation for string functions over single-sorted, total algebraic structures and study some features of a general theory of computability within this framework. Our concept generalizes the Blum-Shub-Smale setting of computability over the reals and other rings. By dealing with strings of arbitrary length instead of tuples of fixed length, some suppositions of deeper results within former approaches to generalized recursion theory become superfluous. Moreover, this gives the basis for introducing computational complexity in a BSS-like manner.Relationships both to classical computability and to Friedman's concept of eds computability are established. Two kinds of nondeterminism as well as several variants of recognizability are investigated with respect to interdependencies on each other and on properties of the underlying structures. For structures of finite signatures, there are universal programs with the usual characteristics. In the general case (of not necessarily finite signature), the existence of universal functions is equivalent to the effective encodability of the structures, whereas the existence of m-complete sets turns out to be independent on those properties.

ICSI Technical Report TR-96-028

Technical Report