On Finitely Presented Expansions of Computably Enumerable Semigroups

by Denis R. Hirschfeldt and Bakhadyr Khoussainov



Status: published in Algebra and Logic 51 (2012) 435 - 444.

Availability: PDF

Abstract. Every computable universal algebra has a finitely presented expansion, but there are examples of finitely generated, computably enumerable universal algebras with no finitely presented expansions. It is natural to ask whether such examples can be found in well-known classes of algebras such as groups and semigroups. In this paper, we build an example of a finitely generated, infinite, computably enumerable semigroup with no finitely presented expansions. We also discuss other interesting computability theoretic properties of this semigroup.



drh@math.uchicago.edu