Abstract Versus Concrete Models of Computation on Partial Metric Algebras

J.V. Tucker & J.I. Zucker

[NOTE: Please address correspondence to the second author]

A model of computation is abstract if, when applied to any algebra, the resulting programs for computable functions and sets on that algebra are invariant under isomorphisms, and hence do not depend on a representation for the algebra. Otherwise it is concrete. Intuitively, concrete models depend on the implementation of the algebra.

The difference is particularly striking in the case of topological partial algebras, and notably in algebras over the reals. We investigate the relationship between abstract and concrete models of partial metric algebras. In the course of this investigation, interesting aspects of continuity, extensionality and non-determinism are uncovered.

Addresses J.V. Tucker: Dept of Computer Science, University of Wales, Swansea SA2 8PP, U.K.

E-mail: J.V.Tucker@swansea.ac.uk

J.I. Zucker: Dept of Computing and Software, McMaster University, Hamilton, Ont. L8S 4L7, Canada

E-mail: zucker@mcmaster.ca