This question is very close to this old MSE question of mine, which is still unanswered.

Is there an (ideally reasonably-natural!) expansion of the structure $(\mathbb{N};+)$ in a finite language whose first-order theory is computable but such that, for each $n$, there is an $n$-quantifier formula not defining the same relation as any $<n$-quantifier formula?

For example, adjoining exponentiation with base $2$ does not work since its quantifier hierarchy collapses (due to Cherlin/Point, see here). Indeed, all the decidability results I'm familiar with for theories of arithmetic rely on quantifier elimination after some finite expansion by definitions, and so won't help here.