I want to ask about decidability of exponential Diophantine equation:
$z_12^{\eta_1} + \ldots + z_n2^{\eta_n} = z$, where $z_i,\eta_i,z \in \mathbb{Z}$, and $\eta_i$ - are variables.
Can we find solution in $\mathbb{Z}$ in general case or this type of equations is undecidable? What you advise to read on this problem?
Very grateful for any help.
Are the $\eta_i$ supposed to be non-negative integers? In any case, writing the $z_i$ as sums of powers of two, i.e., write out their binary expansion, and expanding $z_12^{\eta_1}+\cdots+z_n2^{\eta_n}$, you can reduce to the case that all of the $z_i$ are equal to $\pm1$. So you're asking, for a fixed $m\ge0$ and $n\ge0$, can one determine, for every $z\in\mathbb{Z}$, if $z$ can be expressed in the form $$ z=\hbox{(sum of $n$ powers of 2)}-\hbox{(sum of $m$ powers of 2)} $$ This isn't meant to be a solution, but maybe it's a helpful simplification.
If $\eta_i$ are nonnegative, then there is an algorithm (though not very efficient) finding all the solutions. First note that there is one $\eta_i$ such that $v_2(\eta_i)\le v_2(z)$. where $v_2$ denotes the 2-adic valuation. Then you loop through $1\le i\le n$ and $0\le\eta_i\le v_2(z)$. Plug that $\eta_i$ in and you get an equation with $n-1$ variables. Recurse.
See Section 2 of Semenov's paper "Logical theories of one-place functions on the set of natural numbers".
