[math-fun] Logic puzzle

It is well known that the first-order theory of the non-negative integers with only addition available is decideable, while the theory with addition and multiplication is not. Suppose we have addition and the number of divisors function (often called d(n) or tau(n)). Is the theory then decideable or not? Proof requested. Franklin T. Adams-Watters