Time: Thursday, October 21, 4:30-5:30PM
Speaker: Dario Verta, GWU
Title: Describing properties on magmas
Abstract: We are interested in the computability-theoretic complexity of determining whether an algebraic structure has a certain property, relative to the algorithmic description that presents a structure. We study computable magmas, i.e., those structures that can be presented in terms of a computable domain with a computable binary operation. We establish that certain properties (such as Markov properties) are hard in a given class of computable structures. In particular, we show some examples of Markov properties at higher levels of the arithmetical hierarchy and some involving more than one property.