Computability - Volume 12, issue 3

Authors: Hirst, Jeffry L. | Mummert, Carl

Article Type: Research Article

Abstract: In this paper, methods of second-order and higher-order reverse mathematics are applied to versions of a theorem of Banach that extends the Schröder–Bernstein theorem. Some additional results address statements in higher-order arithmetic formalizing the uncountability of the power set of the natural numbers. In general, the formalizations of higher-order principles here have a Skolemized form asserting the existence of functionals that solve problems uniformly. This facilitates proofs of reversals in axiom systems with restricted choice.

Keywords: Reverse mathematics, Weihrauch reducibility, bijection, metric spaces

DOI: 10.3233/COM-230453

Citation: Computability, vol. 12, no. 3, pp. 203-225, 2023

Authors: Amir, Djamel Eddine | Hoyrup, Mathieu

Article Type: Research Article

Abstract: A compact set has computable type if any homeomorphic copy of the set which is semicomputable is actually computable. Miller proved that finite-dimensional spheres have computable type, Iljazović and other authors established the property for many other sets, such as manifolds. In this article we propose a theoretical study of the notion of computable type, in order to improve our general understanding of this notion and to provide tools to prove or disprove this property. We first show that the definitions of computable type that were distinguished in the literature, involving metric spaces and Hausdorff spaces respectively, are actually …equivalent. We argue that the stronger, relativized version of computable type, is better behaved and prone to topological analysis. We obtain characterizations of strong computable type, related to the descriptive complexity of topological invariants, as well as purely topological criteria. We study two families of topological invariants of low descriptive complexity, expressing the extensibility and the null-homotopy of continuous functions. We apply the theory to revisit previous results and obtain new ones. Show more

Keywords: Computable type, descriptive complexity, topological invariant

DOI: 10.3233/COM-220430

Citation: Computability, vol. 12, no. 3, pp. 227-269, 2023

Authors: Faizrahmanov, Marat

Article Type: Research Article

Abstract: The Arslanov completeness criterion says that a c.e. set A is Turing complete if and only there exists an A -computable function f without fixed points, i.e. a function f such that W f ( x ) ≠ W x for each integer x . Recently, Barendregt and Terwijn proved that the completeness criterion remains true if we replace the Gödel numbering x ↦ W x with an arbitrary precomplete computable numbering. In this paper, we prove criteria for noncomputability and highness of …c.e. sets in terms of (pre)complete computable numberings and fixed point properties. We also find some precomplete and weakly precomplete numberings of arbitrary families computable relative to Turing complete and non-computable c.e. oracles respectively. Show more

Keywords: Arslanov completeness criterion, fixed point, complete numbering, precomplete numbering, weakly precomplete numbering, computable numbering, minimal numbering, high set

DOI: 10.3233/COM-210387

Citation: Computability, vol. 12, no. 3, pp. 271-282, 2023

Authors: Ishkuvatov, Ruslan | Musatov, Daniil | Shen, Alexander

Article Type: Research Article

Abstract: It is well known that the Kolmogorov complexity function (the minimal length of a program producing a given string, when an optimal programming language is used) is not computable and, moreover, does not have computable lower bounds. In this paper we investigate a more general question: can this function be approximated? By approximation we mean two things: firstly, some (small) difference between the values of the complexity function and its approximation is allowed; secondly, at some (rare) points the values of the approximating function may be arbitrary. For some values of the parameters such approximation is trivial (e.g., the …length function is an approximation with error d except for a O ( 2 − d ) fraction of inputs). However, if we require a significantly better approximation, the approximation problem becomes hard, and we prove it in several settings. Firstly, we show that a finite table that provides good approximations for Kolmogorov complexities of n -bit strings, necessarily has high complexity. Secondly, we show that there is no good computable approximation for Kolmogorov complexity of all strings. In particular, Kolmogorov complexity function is neither generically nor coarsely computable, as well as its approximations, and the time-bounded Kolmogorov complexity (for any computable time bound) deviates significantly from the unbounded complexity function. We also prove hardness of Kolmogorov complexity approximation in another setting: the mass problem whose solutions are good approximations for Kolmogorov complexity function is above the halting problem in the Medvedev lattice. Finally, we mention some proof-theoretic counterparts of these results. A preliminary version of this paper was presented at CiE 2019 conference (In Computing with Foresight and Industry – 15th Conference on Computability in Europe, CiE 2019, Durham, UK, July 15–19, 2019, Proceedings (2019 ) 230–239 Springer). Show more

Keywords: Kolmogorov complexity, generic computability, coarse computability, approximation, mass problems

DOI: 10.3233/COM-200302

Citation: Computability, vol. 12, no. 3, pp. 283-297, 2023