Additive systems for $\mathbb{Z}$ are undecidable
Additive systems for $\mathbb{Z}$ are undecidable
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.
Andrei Zabolotskii
数学
Andrei Zabolotskii.Additive systems for $\mathbb{Z}$ are undecidable[EB/OL].(2025-08-24)[2025-09-03].https://arxiv.org/abs/2508.17285.点此复制
评论