Computability on uncountable sets has no standard formalization, unlike that on countable sets, which is given by Turing machines. Some of the approaches to define computability in these sets rely on order-theoretic structures to translate such notions from Turing machines to uncountable spaces. Since these machines are used as a baseline for computability in these approaches, countability restrictions on the ordered structures are fundamental. Here, we aim to combine the theories of computability with order theory in order to study how the usual countability restrictions in these approaches are related to order density properties and functional characterizations of the order structure in terms of multi-utilities.
翻译:与图灵机提供的可计算数据集不同,不可计算数据集的可计算性没有标准的正式化,这些数据集的可计算性定义的一些方法依靠定序理论结构将这种概念从图灵机转换为不可计算空间,由于这些机器被用作这些方法的可计算性基准,定购结构的可计算性限制至关重要。在这里,我们的目标是将可计算性理论与定序理论结合起来,以便研究这些方法中通常的可计算性限制如何与定序结构的密度特性和功能特性(多用途)相联系。