Title: On the relation between representations and computability,
Abstract: One of the fundamental results in computability is the existence of
well-defined functions that cannot be computed. In this paper we study the
effects of data representation on computability; we show that, while for each
possible way of representing data there exist incomputable functions, the
computability of a specific abstract function is never an absolute property,
but depends on the representation used for the function domain. We examine the
scope of this dependency and provide mathematical criteria to favour some
representations over others. As we shall show, there are strong reasons to
suggest that computational enumerability should be an additional axiom for
computation models. We analyze the link between the techniques and effects of
representation changes and those of oracle machines, showing an important
connection between their hierarchies. Finally, these notions enable us to gain
a new insight on the Church-Turing thesis: its interpretation as the underlying
algebraic structure to which computation is invariant.