Compared to Waring's problem, this is potentially much harder, as we can go infinitely negative in our attempts, there isn't a bound on how many tries we can have for each number.
In other words, it is unlikely to have a Conjecture reduction to a halting problem.