J.V. Tucker and J.I. Zucker (2004):
Abstract versus Concrete Computation on Metric Partial Algebras.
ACM Transactions on Computational Logic 5, 611-668.
[preprint.pdf,
[PDF via ACM Portal,
appendix.pdf]
Abstract.
In the theory of computation on topological algebras there is a
considerable gap between so-called abstract and concrete models of
computation. In concrete models,
unlike abstract models,
the computations depend on the representation of the algebra.
First, we show that with abstract models,
one needs algebras with
partial operations, and computable functions that are
both continuous and
many-valued. This many-valuedness is needed even to compute
single-valued functions, and so abstract models must be
nondeterministic even to compute deterministic problems. As an
abstract model, we choose the "while-array" programming language,
extended with a nondeterministic "countable choice" assignment,
called the WhileCC* model. Using this,
we introduce the concept of approximable
many-valued computation on metric algebras.
For our concrete model, we
choose metric algebras with effective representations.
We prove: (1)
for any metric algebra A with an effective representation alpha,
WhileCC* approximability implies computability in alpha,
and (2) also the converse,
under certain reasonable conditions on A.
From (1) and (2) we derive an
equivalence theorem between abstract and concrete computation
on metric partial algebras.
We give examples of algebras where this equivalence holds.