What Turing degrees can truth in $\mathbb{N}$ have for different languages? Tarski’s theorem implies that set of Gödel numbers of statements in the language of Peano arithmetic which are true in $\mathbb{N}$, the standard model of arithmetic, is not a recursive set.  In fact its Turing degree is $0^{‘(\omega)}$.  On the other hand, the set of Gödel numbers of statements in the language of Presburger arithmetic which are true in $\mathbb{N}$ is a recursive set.  
My question is, is there a language $L$ more expressive than the language of Presburger arithmetic, but less expressive than the language of Peano arithmetic, such that the set of Gödel numbers of statements in $L$ which are true in $\mathbb{N}$ has a Turing degree somewhere between $0$ and  $0^{‘(\omega)}$?  Maybe adding to the language of Presburger arithmetic some primitive recursive function that grows faster than addition but slower than multiplication?
If so, what are all the Turing degrees that can be obtained in this way?
 A: Here's a partial affirmative answer. If we go down to the language of order alone, the answer is yes. This is Exercise $1.14(b)$ in Flum's $1974$ paper First-order logic and its extensions. Specifically, we show that $$Th(\omega;<,A)\equiv_TA$$ whenever $A\subseteq\omega$ has increasing distances (that is, if $(a_i)_{i\in\omega}$ enumerates $A$ in order then $a_{n+1}-a_n<a_{n+2}-a_{n+1}$ for all $n$).
Roughly, the idea is to find computably in $A$ a sequence of sets $(B_i)_{i\in\omega}$ such that $$Th(\omega;<,B_i)$$ is computable from $A$ uniformly in $i$ and $(\omega;<,B_i)\equiv_i(\omega;<,A)$. The increasing distance condition lets us do this with eventually-periodic $B$s, the point being that it rules out "noticeable" (e.g. small) intervals in $A$ after the initial segment of $A$ our $B_i$ is trying to "mimic."

But this "limit of increasingly equivalent structures" idea gets a lot harder once the language has function symbols. I suspect that something like it will work, but the relevant "sparseness" condition will have to be more complicated.
