On Algorithmic Properties Of Computable Magmas
Open AccessUsing the notions and methods of computability theory, we study effectiveproperties of computable magmas. A magma is an algebraic structure with asingle binary operation that is not necessarily associative nor commutative.We define a magma to be computable if it is finite or if its domain can beidentified with the set of natural numbers and the magma operation iscomputable. Our main focus is on order relations on magmas, which provide a ranking of the elements of the magma while staying invariant under the magma operation. The algorithmic complexity of additional relations, which are not part of the basic structure, such as orderings of the domain, might change under isomorphic transformations of the structure even if the structure remains computable. We formulate sufficient and necessary algebraic conditions for a binaryrelation to be an order on a given magma. Using these conditions, weconstruct a binary tree to represent the orders on magmas in an informativeand visual way. The tree construction allows us to formulate a necessary andsufficient condition for extending a partial order to a total order. A treerepresentation of a magma's orderings in an effective setting facilitatesanalysis of computability-theoretic complexity of the order relations. We also study geometric properties of the space of orders on a magma using the natural topology defined on binary trees (i.e., Cantor space). We investigate the Turing degrees of left orders, right orders, and bi-orders of orderable magmas from various algebraic classes. We give special attention to classes of self-distributive magmas that comefrom knot theory, known as racks and quandles. At present, very little isknown about their orderability and orders. We consider specific instances of quandles, such as the conjugate quandles of groups. We construct an isomorphic computable copy of the conjugate quandle of the free group with infinitely many generators so that the quandle has no computable right orders. As a corollary, we obtain that the space of right orders on this quandle is homeomorphic to the Cantor set. The same is true for its space of bi-orders.Finally, we study global decision problems for magmas, that is, we ask ifthere is an algorithm capable of deciding whether an arbitrary computablemagma satisfies some specified property. When there is no such algorithm, we ask how hard it is to detect the property in a computability-theoreticsense. Equivalently, we discuss the complexity of index sets of magmas thatsatisfy certain properties within the class of computable magmas. We providesharp characterizations of the algorithmic complexity of detecting manynatural properties of magmas in terms of the arithmetical hierarchy.Properties considered include commutativity, idempotence, rightself-distributivity, orderability, and left-inverse property.
- 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.