Computability theory: countable magmas and their properties
Open AccessThe theory of computability has as its focus the study of algorithms and their properties. Rooted in ancient methods to solve some of humanity’s first arithmetic problems as well as in more contemporary solutions to deep questions about what can be done algorithmically in theory, the results in this theory have far reaching consequences, not least of all the undecidability of the halting problem.One of the main focuses in computability, as in many branches of mathematics, is that of classification. Depending on the nature and scope of the problem at hand, classification may be done according to one of a number of hierarchies, such as the arithmetical hierarchy. We are interested in classifying the difficulty of properties (in particular Markov properties) of certain classes of structures. Just as we can classify properties of structures we can classify the maps between them, though we focus instead on a generic or average case, rather than the “worst-case” complexity when thinking of a particular map later on. We also look into classifying properties of a broad class of structures, computable magmas, by their algorithmic complexity according to certain classes in the arithmetical hierarchy and the Ershov difference hierarchy. In particular, the property of “being a group” and “being a loop” would be our focus. To determine the complexity of the former we make use of a curious definition of being a group that leads to a surprisingly low complexity for this property. On the other hand, we use four different types of amalgamation product in the process of showing the latter is of a somewhat higher algorithmic complexity. Finally, we consider the average case or “generic” complexity of a map between two very similar structures, a group and an almost group.
- All rights reserved
Notice to Authors
If you are the author of this work and you have any questions about the information on this page, please use the Contact form to get in touch with us.