J.V. Tucker and J.I. Zucker (2006):
Abstract versus concrete computability:
The case of countable algebras.
Logic Colloquium '03, Proceedings of the Annual European Summer
Meeting of the Association for Symbolic Logic, Helsinki, August 2003,
ed. V. Stoltenberg-Hansen and J. Väänänen.
Lecture Notes in Logic 24,
Association for Symbolic Logic and A.K. Peters, 377-408.
[preprint.pdf]
Abstract.
We consider the distinction between abstract computability, in
which computation is independent of data representations, and concrete
computability, in which computations are dependent on data
representations. The distinction is useful for current research in
computability theories for continuous data and uncountable structures,
including topological algebras and higher types. The distinction is also
interesting in the seemingly simple case of discrete data and countable
algebras. We give some theorems about equivalences and inequivalences
between abstract models (e.g., computation with 'while' programs) and
concrete models (e.g., computation via numberings) in the countable case.