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

  1. Introduction
  2. Signatures and algebras
  3. `While' computability on standard algebras
  4. Representation of semantic functions; Universality
  5. Notions of semicomputability
  6. Examples of semicomputable sets of real and complex numbers
  7. Computation on topological partial algebras
  8. A survey of models of computability