What is it that makes Th$(ℕ;+)$ and Th$(ℕ;×)$ decidable but makes Th$(ℕ;E)$ undecidable? I know that $+ \ \mathrm{and} ×  \mathrm{are \ definable \ in} \ ⟨ ℕ;E⟩ $, and that Th$(ℕ;+,×)$ is undecidable, but I am trying to get an intuitive idea about what it is that makes theories of structures with certain binary operators (such as $+$ or $×$) decidable while making others (such as $E$) undecidable. 
To avoid a focus on $E$, note that Th$(ℕ; f)$ is also undecidable, where $f$ is a binary operation defined by $f(x,y) = x^{2} + y^{2}$.
To reiterate the observations: 


*

*$+, ×, E,$ and $f$ are all binary operations on $ℕ$.

*Th$(ℕ; +)$ and Th$(ℕ; ×)$ are both decidable.

*Th$(ℕ; E)$ and Th$(ℕ; f)$ are both undecidable. 


What is the property that separates operations like $+$ and $×$ from the ones like $E$ and $f$? 
 A: One key feature of the combination of addition and multiplication is that they allow us to talk about finite sequences. A first step towards seeing this is observing that there is a definable pairing operation in $(\mathbb{N}; +,\times)$, and from there we proceed to Godel's $\beta$-function. By contrast, there is no pairing function definable in $(\mathbb{N}; +)$ alone, let alone something Presburger arithmetic can talk about and prove to be a pairing function, so if we try to talk about finite sequences in Presburger arithmetic we fail miserably. (And the same holds for Skolem arithmetic.)
Coding finite sequences is important since it lets us talk about logic inside our arithmetic system: by representing logical symbols by natural numbers, sentences become finite sequences of natural numbers and proofs become finite sequences of finite sequences of natural numbers, and once we can talk about finite sequences we can collapse all of this to finite sequences alone.
Moreover, once we can talk about finite sequences we can also talk about computable functions in a nice way: every computable $f$ is definable (indeed, representable) in a weak theory of arithmetic using both $+$ and $\times$, essentially because we can talk about a computation consisting of a finite sequence of steps.

So if I want to show that $Th(\mathbb{N}; h)$ is undecidable, the natural thing to do is start by looking for a way to define a pairing function using $h$. Doing that, however, isn't necessarily intuitively clear; e.g. I was rather surprised to hear that $E$ can do it!


*

*Here's a silly observation supporting my claim of non-intuitiveness: whether a given computable (even primitive recursive or better) binary operation on $\mathbb{N}$ yields an undecidable theory is in general undecidable in our favorite background theory. For example, let $K(x,y)=x^2+y^2$ if there is no proof of a contradiction in ZFC of length $<x^2+y^2$, and $K(x,y)=0$ otherwise. Then $Th(\mathbb{N}, K)$ is undecidable iff ZFC is consistent! Now granted this $K$ is extremely artificial, but this does demonstrate that there is some fundamental difficulty at work here.

