Additive systems for $\mathbb{Z}$ are undecidable
For mathematicians and computer scientists, it proves that a natural combinatorial problem about integer representations is undecidable, linking it to long-standing open problems.
The paper shows that determining whether a canonical additive system covers all integers is undecidable, as it is equivalent to the Collatz conjecture and the universal halting problem for Fractran.
What are the collections of sets ${A}_i\subset\mathbb{Z}$ such that any $n\in\mathbb{Z}$ has exactly one representation as $n=a_0+a_1+\dotsb$ with $a_i\in{A}_i$? The answer for $\mathbb{N}_0$ instead of $\mathbb{Z}$ is given by a theorem of de Bruijn. We describe a family of natural candidate collections for $\mathbb{Z}$, which we call canonical collections. Translating the problem into the language of dynamical systems, we show that the question of whether the sumset of a canonical collection covers the entire $\mathbb{Z}$ is difficult: specifically, there is a collection for which this question is equivalent to the Collatz conjecture, and there is a well-behaved family of collections for which this question is equivalent to the universal halting problem for Fractran and is therefore undecidable.