Premium
Computability of String Functions Over Algebraic Structures Armin Hemmerling
Author(s) -
Hemmerling Armin
Publication year - 1998
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.19980440102
Subject(s) - computability , computability theory , computable function , mathematics , string (physics) , recursion (computer science) , algebraic number , discrete mathematics , algebra over a field , pure mathematics , algorithm , mathematical analysis , mathematical physics
Abstract We present a model of computation for string functions over single‐sorted, total algebraic structures and study some basic 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. For the general case of not necessarily finite signature, this subject will be studied in a separate, forthcoming paper.