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).
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