EUVIMEDEUVIMED entdecken
Crossref

Additive systems for \(\mathbb{Z}\) are undecidable

Andrei Zabolotskii

Journal of Combinatorial Mathematics and Combinatorial Computing · 11.04.2026 · 130 · 241-253

DOI: 10.61091/jcmcc130-16 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Combinatorial Mathematics and Combinatorial Computing, online erschienen am 11.04.2026. Verfasst von Andrei Zabolotskii.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Zabolotskii, A. (2026). Additive systems for \(\mathbb{Z}\) are undecidable. Journal of Combinatorial Mathematics and Combinatorial Computing, 130, 241-253. https://doi.org/10.61091/jcmcc130-16

Vancouver

Zabolotskii A. Additive systems for \(\mathbb{Z}\) are undecidable. Journal of Combinatorial Mathematics and Combinatorial Computing. 2026;130:241-253. doi:10.61091/jcmcc130-16

BibTeX
@article{Zabolotskii2026,
  author = {Zabolotskii, Andrei},
  title = {Additive systems for \(\mathbbZ\) are undecidable},
  journal = {Journal of Combinatorial Mathematics and Combinatorial Computing},
  year = {2026},
  volume = {130},
  pages = {241--253},
  doi = {10.61091/jcmcc130-16}
}
Kostenlos starten →