  Although there is a somewhat standard formalization of computability on
countable sets given by Turing machines, the same cannot be said about
uncountable sets. Among the approaches to define computability in these sets,
order-theoretic structures have proven to be useful. Here, we discuss the
mathematical structure needed to define computability using order-theoretic
concepts. In particular, we introduce a more general framework and discuss its
limitations compared to the previous one in domain theory. We expose four
features in which the stronger requirements in the domain-theoretic structure
allow to improve upon the more general framework: computable elements,
computable functions, model dependence of computability and complexity theory.
Crucially, we show computability of elements in uncountable spaces can be
defined in this new setup, and argue why this is not the case for computable
functions. Moreover, we show the stronger setup diminishes the dependence of
computability on the chosen order-theoretic structure and that, although a
suitable complexity theory can be defined in the stronger framework and the
more general one posesses a notion of computable elements, there appears to be
no proper notion of element complexity in the latter.
