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.
翻译:虽然图灵机器给出的可计算数据集的计算格式有些标准化,但无法对不可计算数据集作出同样的说法。在界定这些数据集的可计算性的方法中,秩序理论结构证明是有益的。在这里,我们讨论使用定序理论概念界定可计算性所需的数学结构。特别是,我们引入了一个较一般性的框架,并讨论其与先前的域论理论相比的局限性。我们暴露了四个特点,其中域理论结构中较强的要求使得能够改进较一般性的框架:可计算要素、可计算函数、可计算要素的模型依赖性和复杂理论。 关键是,我们展示了不可计算空间要素的可计算性,可以在新的设置中加以界定,并论证为什么这不是可计算功能的参数。此外,我们展示了较强的设置减少了对所选择的定序结构的可比较性的依赖性,而且尽管在较强的框架中可以界定出一种适当的复杂理论,而较笼统的理论则构成可计算要素的概念,但在后一个要素中似乎没有适当的复杂因素。