论文标题
计算作为降低不确定性：简化的订单理论框架
Computation as uncertainty reduction: a simplified order-theoretic framework
论文作者
论文摘要
尽管在图灵机给出的可计数集上有一定标准的可计算性形式化，但对于无数组合，却不能说同样的话。在这些集合中定义可计算性的方法中，订单理论结构已被证明是有用的。在这里，我们讨论使用订单理论概念定义可计算性所需的数学结构。特别是，我们引入了一个更一般的框架，并讨论了与域理论中的前一个相比的局限性。我们揭示了四个功能，其中域理论结构中更强大的要求可以改善更一般的框架：可计算元素，可计算函数，计算性和复杂性理论的模型依赖性。至关重要的是，我们可以在此新设置中表明可以定义无数空间中元素的可计算性，并争论为什么可计算功能不是这种情况。此外，我们显示的设置较强会降低计算性对所选顺序理论结构的依赖性，尽管可以在更强的框架中定义合适的复杂性理论，并且越广泛地提出了可计算元素的概念，但后者似乎没有适当的元素复杂性概念。
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.
