Computability - Volume 13, issue 3-4

Authors: Berger, Ulrich | Franklin, Johanna N.Y. | Mayordomo, Elvira

Article Type: Editorial

DOI: 10.3233/COM-249534

Citation: Computability, vol. 13, no. 3-4, pp. 197-198, 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. 13, no. 3-4, pp. 199-222, 2024

Authors: Banakh, Taras | Lubarsky, Robert S.

Article Type: Research Article

Abstract: Topological models are sometimes used to prove independence results in constructive mathematics. Here we show that some of the topologies that have been used are necessary for those results.

Keywords: Constructive mathematics, topological models

DOI: 10.3233/COM-230443

Citation: Computability, vol. 13, no. 3-4, pp. 223-236, 2024

Authors: Berger, Julian | Böther, Maximilian | Doskoč, Vanja | Gadea Harder, Jonathan | Klodt, Nicolas | Kötzing, Timo | Lötzsch, Winfried | Peters, Jannik | Schiller, Leon | Seifert, Lars | Wells, Armin | Wietheger, Simon

Article Type: Research Article

Abstract: We study learning of indexed families from positive data where a learner can freely choose a hypothesis space (with uniformly decidable membership) comprising at least the languages to be learned. This abstracts a very universal learning task which can be found in many areas, for example learning of (subsets of) regular languages or learning of natural languages. We are interested in various restrictions on learning, such as consistency, conservativeness or set-drivenness, exemplifying various natural learning restrictions. The contribution of this work is twofold. First, we present a general result on how the hypothesis spaces may be constructed during …learning, rather than beforehand. Using this result, we build on previous results from the literature and provide several maps (depictions of all pairwise relations) of various groups of learning criteria, including a map for monotonicity restrictions and similar criteria and a map for restrictions on data presentation. Furthermore, we consider, for various learning criteria, whether learners can be assumed consistent. Show more

Keywords: Language learning in the limit, indexed family, hypothesis space, map, characteristic index

DOI: 10.3233/COM-220421

Citation: Computability, vol. 13, no. 3-4, pp. 237-261, 2024

Authors: Blechschmidt, Ingo | Schuster, Peter

Article Type: Research Article

Abstract: The existence of a maximal ideal in a general nontrivial commutative ring is tied together with the axiom of choice. Following Berardi, Valentini and thus Krivine but using the relative interpretation of negation (that is, as “implies 0 = 1 ”) we show, in constructive set theory with minimal logic, how for countable rings one can do without any kind of choice and without the usual decidability assumption that the ring is strongly discrete (membership in finitely generated ideals is decidable). By a functional recursive definition we obtain a maximal ideal in the sense that the quotient ring is …a residue field (every noninvertible element is zero), and with strong discreteness even a geometric field (every element is either invertible or else zero). Krull’s lemma for the related notion of prime ideal follows by passing to rings of fractions. By employing a construction variant of set-theoretic forcing due to Joyal and Tierney, we expand our treatment to arbitrary rings and establish a connection with dynamical algebra: We recover the dynamical approach to maximal ideals as a parametrized version of the celebrated double negation translation. This connection allows us to give formal a priori criteria elucidating the scope of the dynamical method. Along the way we do a case study for proofs in algebra with minimal logic, and generalize the construction to arbitrary inconsistency predicates. A partial Agda formalization is available at an accompanying repository.1 1 See https://github.com/iblech/constructive-maximal-ideals/ . This text is a revised and extended version of the conference paper (In Revolutions and Revelations in Computability. 18th Conference on Computability in Europe (2022) Springer). The conference paper only briefly sketched the connection with dynamical algebra; did not compare this connection with other flavors of set-theoretic forcing; and sticked to the case of commutative algebra only, passing on the generalization to inconsistency predicates and well-orders. See https://github.com/iblech/constructive-maximal-ideals/ . This text is a revised and extended version of the conference paper (In Revolutions and Revelations in Computability. 18th Conference on Computability in Europe (2022) Springer). The conference paper only briefly sketched the connection with dynamical algebra; did not compare this connection with other flavors of set-theoretic forcing; and sticked to the case of commutative algebra only, passing on the generalization to inconsistency predicates and well-orders. Show more

Keywords: Maximal ideals, set-theoretic forcing, constructive commutative algebra, dynamical algebra

DOI: 10.3233/COM-230454

Citation: Computability, vol. 13, no. 3-4, pp. 263-297, 2024

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. 13, no. 3-4, pp. 299-324, 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. 13, no. 3-4, pp. 325-348, 2024

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. 13, no. 3-4, pp. 349-361, 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. 13, no. 3-4, pp. 363-375, 2024

Authors: Hella, Lauri | Vilander, Miikka

Article Type: Research Article

Abstract: We consider the length of the longest word definable in FO and MSO via a formula of size n . For both logics we obtain as an upper bound for this number an exponential tower of height linear in n . We prove this by counting types with respect to a fixed quantifier rank. As lower bounds we obtain for both FO and MSO an exponential tower of height in the order of a rational power of n . We show these lower bounds by giving concrete formulas defining word representations of levels of the cumulative hierarchy of sets. For …the two-variable fragment of FO we obtain quadratic lower and upper bounds for the definability numbers of quantifier rank k fragments. In addition, we consider the Löwenheim–Skolem and Hanf numbers of these logics on words and obtain similar bounds for these as well. Show more

Keywords: Logic on words, monadic second-order logic, succinctness

DOI: 10.3233/COM-230450

Citation: Computability, vol. 13, no. 3-4, pp. 377-398, 2024