J.V. Tucker and J.I. Zucker (1998):
Computable functions and semicomputable sets on many-sorted algebras,
McMaster University, Dept of Computer Science, Technical Report 98-01;
to appear in
Handbook of Logic in Computer Science, Vol. 5,
ed. S. Abramsky, D.M. Gabbay and T.S.E. Maibaum
(Oxford University Press).
[
preprint.ps]
Abstract.
This is an introduction to the theory of functions and sets
that are computable by algorithms defined on arbitrary
many-sorted algebras. The algorithms are formalised by
means of imperative programming languages, including
languages based on the `while' construct, with and without
arrays.
The basic properties and results about computable functions (e.g., universality theorems) and semicomputability (e.g., definability) are treated in detail.
There is a study of computable functions on algebras of real numbers. This is generalised to a new account of functions that are computable and computably approximable on topological partial algebras.
A survey of other models of computation and appropriate
equivalence theorems for abstract algebras is provided.
Also included are accounts of connections with the theories
of computable algebra and computable analysis, and a short
history of generalisations of computability theory to
algebras.
Contents