Reducibilities among decision problems for HNN groups, vector addition systems and subsystems of Peano arithmetic
Michael Anshel, Kenneth McAloon · Proceedings of the American Mathematical Society · 1983
Our purpose is to exhibit reducibilities among decision problems for conjugate powers in HNN groups, reachability sets of vector addition systems and sentences in subsystems of Peano arithmetic, and show that although these problems are not primitive recursively decidable, they do admit decision procedures which are primitive recursive in the Ackermann function.