Finitely presented group with intermediate Turing degree word problem

133 Views Asked by At

Does there exist a finitely presented group with undecidable word problem, but so that an oracle to solve the word problem for this group wouldn't be sufficient to solve the halting problem in general?

I'd imagine there's no known example, as there aren't "natural" problems we know of that are undecidable but less hard than the halting problem, although maybe there is some argument against that possibility here, or at least a reason we should expect things to go one way or another.

2

There are 2 best solutions below

1
On BEST ANSWER

There might not be specific known examples, but https://en.wikipedia.org/wiki/Word_problem_for_groups gives an example of a mapping from a set $A\subseteq \mathbb{N}$ to a group $G: \langle a,b,c,d| a^nba^n=c^ndc^n , n\in A\rangle$ with presumably the same complexity for its word problem. This group isn't FP, but there's also mention in that article that every FG group with recursively enumerable presentation is a subgroup of a FP group with insoluble word problem; I would suggest checking the references to see if that construction maintains complexity, since that would give your answer.

0
On

Having a decidable word problem for a recursively presented group is a $\Sigma^0_3$ (complete) property, whereas the Halting set is $\Sigma^0_1$ complete, so necessarily any oracle that decides on the first will decide on the Halting problem, I am pretty sure.