Classical computability theory ("recursion theory") deals with computation on the natural numbers, or on strings over a finite alphabet, as developed by Turing, Kleene, Church and others, starting in the 1930s.
These lectures will deal with a generalisation of this classical theory to arbitrary many-sorted ("abstract") algebras. The algorithms are formalised by means of imperative programming languages based on the `while' construct, with and without arrays.
The basic properties and results about computable functions (e.g., universality theorems) and semicomputable sets (e.g., definability) will be treated. In particular, we will consider computability on the real numbers, and (if time permits) a theory of "approximable computability" on the reals, and (more generally) on topological partial algebras.
This is based on joint research with J.V. Tucker.
The course notes will consist of the report [TZ].
Prerequisite: Basic knowledge of classical computability theory ("recursion theory"), such as may be found in Secs. 1 - 14 of the article [ZP], copies of which will be available at the meeting.
REFERENCES
(NOTE: Both these articles are available from my web site http://www.cas.mcmaster.ca/~zucker/Pubs/ .)
[TZ] J.V. Tucker and J.I. Zucker (1998): Computable functions and semicomputable sets on many-sorted algebras, McMaster University, Dept of Computer Science, Report 98-01; to appear in the Handbook of Logic in Computer Science, Vol. 5, ed. S. Abramsky, D.M. Gabbay and T.S.E. Maibaum (Oxford Univ. Press)
[ZP] J.I. Zucker and L. Pretorius (1993): Introduction to computability theory, South African Computer Journal, 9, April 1993, 3-30.