20.33 (2022)

(A. Bauer). Does Higman’s Embedding Theorem relativize in the following way? Is it the case that for every subset $X \subseteq \mathbb{N}$, there is a finitely generated group $G_X$ that has an $X$-computable presentation (that is, there is a finite generating set relative to which the set of relations is computably enumerable with an $X$ oracle), and such that any finitely generated group has an $X$-computable presentation if and only if it can be embedded as a finitely generated subgroup of a quotient of a free product of finitely many copies of $G_X$ by the normal closure of a finite subset?

Higman’s Embedding Theorem says that for computable $X$, one may take $G_X = \mathbb{Z}$.