Computability - Volume Pre-press, issue Pre-press

Authors: Downey, Rodney G. | Greenberg, Noam | Tanggara, Andrew

Article Type: Research Article

Abstract: Rademacher (Mathematische Annalen 87 (1922) 112–138), Steinhaus (Mathematische Zeitschrift 31 (1930) 408–416) and Paley and Zygmund (Mathematical Proceedings of the Cambridge Philosophical Society 26 (1930) 337–257, Mathematical Proceedings of the Cambridge Philosophical Society 26 (1930) 458–474, Mathematical Proceedings of the Cambridge Philosophical Society 28 (1932) 190–205) initiated the extensive study of random series. Using the theory of algorithmic randomness, which is a mix of computability theory and probability theory, we investigate the effective content of some classical theorems. We discuss how this is related to an old question of Kahane …and Bollobás. We also discuss how considerations of such algorithmic questions about random series seem to lead to new notions of algorithmic randomness. Show more

Keywords: Algorithmic randomness, random trigonometric series, Schnorr randomness, Kurtz randomness, Martin-Löf randomness, Payley–Zygmund series, Rademacher series

DOI: 10.3233/COM-220433

Citation: Computability, vol. Pre-press, no. Pre-press, pp. 1-13, 2023

Authors: Carl, Merlin

Article Type: Research Article

Abstract: This paper extends our paper (In Revolutions and Revelations in Computability. CiE 2022 (2022 )) for the conference “Computability in Europe” 2022. After Infinite Time Turing Machines (ITTM) were introduced in Hamkins and Lewis (Journal of Symbolic Logic 65 (2000 )), a number of machine models of computability have been generalized to the transfinite. While for some of these models the computational strength has been successfully determined, there are still several white spots on the map of transfinite computability. In this paper, we contribute to the understanding of the computational strength of transfinite machine models by …(i) proving lower bounds on the computational strength of α -Infinite Time Register Machines (α -ITRMs) for certain values of α , refuting a conjecture about their strength made in (Annals of Pure and Applied Logic 173 (2022 )), (ii) showing that the computational strength of cardinal-recognizing ITRMs is equal to that of ITRMs and (iii) showing that non-solvability of the bounded halting problem, existence of a universal machine and an increase of computational power by allowing machines to recognize cardinals are equivalent for α -ITRMs for all relevant values of α . Finally, we give some results indicating how the picture changes when the use of parameters is dropped or restricted. Show more

Keywords: Ordinal computability, Infinite Time Register Machines, Gandy ordinals

DOI: 10.3233/COM-230439

Citation: Computability, vol. Pre-press, no. Pre-press, pp. 1-26, 2024

Authors: Georgiev, Ivan

Article Type: Research Article

Abstract: The topic of this paper is the study of the possibility of effective conversions between different representations of irrational numbers. We are interested in subrecursive computations, in which we disallow the use of unbounded search. It is well-known that the base expansion of an irrational number can be subrecursively computed from its Dedekind cut, but in the reverse direction this is not subrecursively possible. Thus it would be natural to try to understand how additional properties of the base expansion, such as the presence of specific patterns of zero digits, correlate with the complexity of the Dedekind cut. Our first …result roughly states that if large parts of zero digits dominate over smaller parts of arbitrary digits and the base expansion has elementary complexity, then the Dedekind cut also has elementary complexity. Much more interesting is the case when one allows large parts of zero digits to alternate with large parts of arbitrary digits. We compare the complexity of the Dedekind cuts of an arbitrary irrational number and another irrational number, obtained by inserting long sequences of zero digits in its base expansion. We provide examples in which (1) both numbers have elementary Dedekind cuts, (2) the first number has complex Dedekind cut and elementary base expansion, but the second number has elementary Dedekind cut and (3) both numbers have complex Dedekind cuts and elementary base expansions. An open question remains, whether it is possible for the first number to have elementary Dedekind cut, while the second number has complex Dedekind cut. Show more

Keywords: Irrational number representations, base expansions, Dedekind cuts, subrecursive classes, computable analysis

DOI: 10.3233/COM-230469

Citation: Computability, vol. Pre-press, no. Pre-press, pp. 1-25, 2024

Authors: Anselmo, Marcella | Flores, Manuela | Madonia, Maria

Article Type: Research Article

Abstract: Isometric words are those words whose occurrence as a factor in a transformation of a word u in a word v can be avoided, while preserving the minimal length of the transformation. Such minimal length refers to a distance between u and v . In the literature, isometric words have been considered with respect to the Hamming distance and the Lee distance; the former especially for binary words, while the latter for k -ary words, with k ⩾ 2 . Ham- and Lee- isometric words have been characterized in terms of their overlaps with …errors. In this paper, we give algorithms to decide whether a word f , of length n , is Ham- or Lee-isometric and provide evidence of the possible non-isometricity by returning a pair of words of minimal length whose transformation cannot avoid the factor f . Such a pair of words is called a pair of witnesses and the minimal length of the witnesses is called the index of f . The algorithms run in O ( n ) time with a preprocessing of O ( n ) time and space to construct a data structure that allows answering LCA queries on the suffix tree of f in constant time. The correctness of the algorithms lies on some theoretical results on the index and the witnesses of a word that are here presented. The investigation on the index is completed by the characterization of words with minimum/maximum index. All the results are shown referring to both Hamming and Lee distance. Show more

Keywords: Isometric words, words avoiding factors, index of a word, overlap, Hamming and Lee distances, k-ary n-cube

DOI: 10.3233/COM-230441

Citation: Computability, vol. Pre-press, no. Pre-press, pp. 1-24, 2024

Authors: de Brecht, Matthew | Kihara, Takayuki | Selivanov, Victor

Article Type: Research Article

Abstract: The well known ideal presentations of countably based domains were recently extended to (effective) quasi-Polish spaces. Continuing these investigations, we explore some classes of effective quasi-Polish spaces. In particular, we prove an effective version of the domain-characterization of quasi-Polish spaces, describe effective extensions of quasi-Polish topologies, discover natural numberings of classes of effective quasi-Polish spaces, estimate the complexity of the (effective) homeomorphism relation and of some classes of spaces with respect to these numberings, and investigate degree spectra of continuous domains.

Keywords: Effective quasi-Polish space, effective domain, numbering, index set, degree spectrum

DOI: 10.3233/COM-230442

Citation: Computability, vol. Pre-press, no. Pre-press, pp. 1-24, 2024

Authors: Dzhafarov, Damir D. | Solomon, Reed | Yokoyama, Keita

Article Type: Research Article

Abstract: We introduce the notion of the first-order part of a problem in the Weihrauch degrees. Informally, the first-order part of a problem P is the strongest problem with codomaixn ω that is Weihrauch reducible to P . We show that the first-order part is always well-defined, examine some of the basic properties of this notion, and characterize the first-order parts of several well-known problems from the literature.

DOI: 10.3233/COM-230446

Citation: Computability, vol. Pre-press, no. Pre-press, pp. 1-13, 2024

Authors: Sanders, Sam

Article Type: Research Article

Abstract: Kleene’s computability theory based on the S1–S9 computation schemes constitutes a model for computing with objects of any finite type and extends Turing’s ‘machine model’ which formalises computing with real numbers . A fundamental distinction in Kleene’s framework is between normal and non-normal functionals where the former compute the associated Kleene quantifier ∃ n and the latter do not. Historically, the focus was on normal functionals, but recently new non-normal functionals have been studied based on well-known theorems, the weakest among which seems to be the uncountability of the …reals . These new non-normal functionals are fundamentally different from historical examples like Tait’s fan functional: the latter is computable from ∃ 2 , while the former are computable in ∃ 3 but not in weaker oracles. Of course, there is a great divide or abyss separating ∃ 2 and ∃ 3 and we identify slight variations of our new non-normal functionals that are again computable in ∃ 2 , i.e. fall on different sides of this abyss. Our examples are based on mainstream mathematical notions, like quasi-continuity , Baire classes , bounded variation , and semi-continuity from real analysis. Show more

Keywords: Kleene computability theory, fan functional, non-normal functionals, S1–S9, real analysis

DOI: 10.3233/COM-230475

Citation: Computability, vol. Pre-press, no. Pre-press, pp. 1-22, 2024

Authors: Lutz, Jack H. | Qi, Renrui | Yu, Liang

Article Type: Research Article

Abstract: We prove that, for every 0 ⩽ s ⩽ 1 , there is a Hamel basis of the vector space of reals over the field of rationals that has Hausdorff dimension s . The logic of our proof is of particular interest. The statement of our theorem is classical; it does not involve the theory of computing. However, our proof makes essential use of algorithmic fractal dimension–a computability-theoretic construct–and the point-to-set principle of J. Lutz and N. Lutz (2018).

Keywords: Algorithmic fractal dimension, Hamel bases, Hausdorff dimension, Point-to-Set Principle

DOI: 10.3233/COM-210383

Citation: Computability, vol. Pre-press, no. Pre-press, pp. 1-8, 2024

Authors: Misselbeck-Wessel, Daniel | Petrakis, Iosif

Article Type: Research Article

Abstract: We study the two algebras of complemented subsets that were introduced in the constructive development of the Daniell approach to measure and integration within Bishop-style constructive mathematics. We present their main properties both for the so-called here categorical complemented subsets and for the extensional complemented subsets. We translate constructively the classical bijection between subsets and Boolean-valued, total functions by establishing a bijection between complemented subsets (categorical or extensional) and Boolean-valued, partial functions (categorical or extensional). The role of Myhill’s axiom of non-choice in the equivalence between categorical and extensional subsets is discussed. We introduce swap algebras of type (I) and …(II) as an abstract version of Bishop’s algebras of complemented subsets of type (I) and (II), respectively, and swap rings as an abstract version of the structure of Boolean-valued partial functions on a set. Our examples of swap algebras and swap rings together with the included here results indicate that their theory is a certain generalisation of the theory of Boolean algebras and Boolean rings, a fact which we find interesting both from a constructive and a classical point of view. Show more

Keywords: Constructive mathematics, Bishop set theory, complemented subsets, partial functions, swap algebras

DOI: 10.3233/COM-230462

Citation: Computability, vol. Pre-press, no. Pre-press, pp. 1-33, 2024

Authors: Normann, Dag

Article Type: Research Article

Abstract: Non-monotone inductive definitions were studied in the late 1960’s and early 1970’s with the aim of understanding connections between the complexity of the formulas defining the induction steps and the ordinals measuring the rank of the inductive process. In general, any type 2 functional will generate an inductive process, and in this paper we will view non-monotone induction as a functional of type 3. We investigate the associated computation theory of this functional inherited from the Kleene schemes and we investigate the associated companion of sets with codes computable in the functional of non-monotone induction. The interest in this functional …is motivated from observing that constructions via non-monotone induction appear to be natural in classical analysis. There are two groups of results: We establish strong closure properties of the least ordinal without a code computable in the functional of non-monotone induction, and we provide a characterisation of the class of functionals of type 3 computable from this functional, a characterisation in terms of sequential operators working in transfinite time. We will also see that the full computational power of non-monotone induction is required when this principle is used to construct functionals witnessing the compactness of the Cantor space and of closed, bounded intervals. Show more

Keywords: Non-monotone induction, Kleene computability, sequential procedures, reflection properties

DOI: 10.3233/COM-200321

Citation: Computability, vol. Pre-press, no. Pre-press, pp. 1-36, 2024