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.
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.