Search

We contribute to a recent research program which aims at revisiting the study of the complexity of word problems, a major area of research in combinatorial algebra, through the lens of the theory of computably enumerable equivalence relations (ceers), which has considerably grown in recent times. To pursue our analysis, we rely on the most popular way of assessing the complexity of ceers, that is via computable reducibility on equivalence relations, and its corresponding degree structure (the c -degrees). On the negative side, building on previous work of Kasymov and Khoussainov, we individuate a collection of c -degrees of ceers which cannot be realized by the word problem of any finitely generated algebra of finite type. On the positive side, we show that word problems of finitely generated semigroups realize a collection of c -degrees which embeds rich structures and is large in several reasonable ways. [ABSTRACT FROM AUTHOR]

Artificial intelligence plays an important role in contemporary medicine. In this short note, we emphasize that philosophy played a role in the development of artificial intelligence. We argue that research in computability theory, the theoretical foundation of modern computer science, was motivated by a philosophical question: can we characterize precisely the class of problems that can be solved by algorithms? We suggest that reflecting on the connection between philosophy and artificial intelligence helps realize that philosophical and scientific progress are connected. [ABSTRACT FROM AUTHOR]

This note addresses the issue as to which ceers can be realized by word problems of computably enumerable (or, simply, c.e.) structures (such as c.e. semigroups, groups, and rings), where being realized means to fall in the same reducibility degree (under the notion of reducibility for equivalence relations usually called "computable reducibility"), or in the same isomorphism type (with the isomorphism induced by a computable function), or in the same strong isomorphism type (with the isomorphism induced by a computable permutation of the natural numbers). We observe, e.g., that every ceer is isomorphic to the word problem of some c.e. semigroup, but (answering a question of Gao and Gerdes) not every ceer is in the same reducibility degree of the word problem of some finitely presented semigroup, nor is it in the same reducibility degree of some non‐periodic semigroup. We also show that the ceer provided by provable equivalence of Peano Arithmetic is in the same strong isomorphism type as the word problem of some non‐commutative and non‐Boolean c.e. ring. [ABSTRACT FROM AUTHOR]

In this paper we argue, against a somewhat standard view, that pragmatic phenomena occur in mathematical language. We provide concrete examples supporting this thesis. [ABSTRACT FROM AUTHOR]

The complexity of equivalence relations has received much attention in the recent literature. The main tool for such endeavour is the following reducibility: given equivalence relations R and S on natural numbers, R is computably reducible to S if there is a computable function f : ω → ω that induces an injective map from R-equivalence classes to S-equivalence classes. In order to compare the complexity of equivalence relations which are computable, researchers considered also feasible variants of computable reducibility, such as the polynomial-time reducibility. In this work, we explore Peq, the degree structure generated by primitive recursive reducibility on primitive recursive equivalence relations with infinitely many equivalence classes. In contrast with all other known degree structures on equivalence relations, we show that Peq has much more structure: e.g., we show that it is a dense distributive lattice. On the other hand, we also offer evidence of the intricacy of Peq, proving, e.g., that the structure is neither rigid nor homogeneous. [ABSTRACT FROM AUTHOR]

The relation between semantics and pragmatics is, as Ranta shows, very delicate. If one considers pragmatics as a wastebasket, then the phenomena that we tried to unveil trivially fall into semantics, just because there is no room within pragmatics for a meaningful philosophical analysis. Yet the study of the many facets of mathematical language is to some extent independent from having a robust classification of what should count as semantics and what as pragmatics - even though such a classification would be certainly desirable. [Extracted from the article]

Computably enumerable equivalence relations (ceers) received a lot of attention in the literature. The standard tool to classify ceers is provided by the computable reducibility ⩽ c . This gives rise to a rich degree structure. In this paper, we lift the study of c-degrees to the Δ 2 0 case. In doing so, we rely on the Ershov hierarchy. For any notation a for a non-zero computable ordinal, we prove several algebraic properties of the degree structure induced by ⩽ c on the Σ a - 1 \ Π a - 1 equivalence relations. A special focus of our work is on the (non)existence of infima and suprema of c-degrees. [ABSTRACT FROM AUTHOR]

We study degree spectra of structures with respect to the bi‐embeddability relation. The bi‐embeddability spectrum of a structure is the family of Turing degrees of its bi‐embeddable copies. To facilitate our study we introduce the notions of bi‐embeddable triviality and basis of a spectrum. Using bi‐embeddable triviality we show that several known families of degrees are bi‐embeddability spectra of structures. We then characterize the bi‐embeddability spectra of linear orderings and study bases of bi‐embeddability spectra of strongly locally finite graphs. [ABSTRACT FROM AUTHOR]

Computable reducibility is a well-established notion that allows to compare the complexity of various equivalence relations over the natural numbers. We generalize computable reducibility by introducing degree spectra of reducibility and bi-reducibility. These spectra provide a natural way of measuring the complexity of reductions between equivalence relations. We prove that any upward closed collection of Turing degrees with a countable basis can be realised as a reducibility spectrum or as a bi-reducibility spectrum. We show also that there is a reducibility spectrum of computably enumerable equivalence relations with no countable basis and a reducibility spectrum of computably enumerable equivalence relations which is downward dense, thus has no basis. [ABSTRACT FROM AUTHOR]

We study algorithmic learning of algebraic structures. In our framework, a learner receives larger and larger pieces of an arbitrary copy of a computable structure and, at each stage, is required to output a conjecture about the isomorphism type of such a structure. The learning is successful if the conjectures eventually stabilize to a correct guess. We prove that a family of structures is learnable if and only if its learning domain is continuously reducible to the relation E 0 of eventual agreement on reals. This motivates a novel research program, that is, using descriptive set theoretic tools to calibrate the (learning) complexity of nonlearnable families. Here, we focus on the learning power of well-known benchmark Borel equivalence relations (i.e., E 1 , E 2 , E 3 , Z 0 , and E s e t). [ABSTRACT FROM AUTHOR]

We combine computable structure theory and algorithmic learning theory to study learning of families of algebraic structures. Our main result is a model-theoretic characterization of the learning type Inf Ex ≅ , consisting of the structures whose isomorphism types can be learned in the limit. We show that a family of structures is Inf Ex ≅ -learnable if and only if the structures can be distinguished in terms of their Σ 2 inf -theories. We apply this characterization to familiar cases and we show the following: there is an infinite learnable family of distributive lattices; no pair of Boolean algebras is learnable; no infinite family of linear orders is learnable. [ABSTRACT FROM AUTHOR]

We investigate the complexity of embeddings between bi-embeddable structures. In analogy with categoricity spectra, we define the bi-embeddable categoricity spectrum of a structure A as the family of Turing degrees that compute embeddings between any computable bi-embeddable copies of A ; the degree of bi-embeddable categoricity of A is the least degree in this spectrum (if it exists). We extend many known results about categoricity spectra to the case of bi-embeddability. In particular, we exhibit structures without degree of bi-embeddable categoricity, and we show that every degree d.c.e above 0 (α) for α a computable successor ordinal and 0 (λ) for λ a computable limit ordinal is a degree of bi-embeddable categoricity. We also give examples of families of degrees that are not bi-embeddable categoricity spectra. [ABSTRACT FROM AUTHOR]

We study the algorithmic complexity of embeddings between bi-embeddable equivalence structures. We define the notions of computable bi-embeddable categoricity, (relative) Δ α 0 bi-embeddable categoricity, and degrees of bi-embeddable categoricity. These notions mirror the classical notions used to study the complexity of isomorphisms between structures. We show that the notions of Δ α 0 bi-embeddable categoricity and relative Δ α 0 bi-embeddable categoricity coincide for equivalence structures for α = 1 , 2 , 3 . We also prove that computable equivalence structures have degree of bi-embeddable categoricity 0 , 0 ′ , or 0 ′ ′ . We furthermore obtain results on the index set complexity of computable equivalence structure with respect to bi-embeddability. [ABSTRACT FROM AUTHOR]