Computation as uncertainty reduction: a simplified order-theoretic framework

arXiv2206.13885MaRDI QIDQ6403372FDOQ6403372

Authors: Pedro Hack, Daniel A. Braun, Sebastian Gottwald 

Publication date: 28 June 2022

Abstract: 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.

This page was built for publication: Computation as uncertainty reduction: a simplified order-theoretic framework

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6403372)