###
COMPUTABILITY ON ABSTRACT ALGEBRAS

####
Jeff Zucker

ABSTRACT (Preliminary version)
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.