J.V. Tucker and J.I. Zucker (2002):
Abstract computability and algebraic specification,
ACM Transactions on Computational Logic, 3, 279-333.
[preprint.pdf,
PDF via ACM Portal,
Abstract.
Abstract computable functions are defined by abstract finite
deterministic algorithms on many-sorted algebras. We show
that there exist finite universal algebraic specifications
that specify uniquely (up to isomorphism) (i) all abstract
computable functions on any many-sorted algebra; and
(ii) all functions effectively approximable by abstract
computable functions on any metric algebra.
We show that there exist universal algebraic specifications
for all the classically computable functions on the set R of
real numbers. The algebraic specifications used are mainly
bounded universal equations and conditional equations.
We investigate the initial algebra semantics of these
specifications, and derive situations where algebraic
specifications define precisely the computable functions.