🔢 mathematics

Additive systems for $\mathbb{Z}$ are undecidable

Dit artikel toont aan dat het bepalen of de som van een canonieke verzameling het gehele getallenverzameling $\mathbb{Z}$ overdekt, onbeslisbaar is, aangezien dit probleem equivalent is aan de Collatcg-conjectuur en het universele haltingprobleem voor Fractran.

Oorspronkelijke auteurs: Andrei Zabolotskii

Gepubliceerd 2026-04-01

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Andrei Zabolotskii

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

De Onoplosbare Raadsels van de Getallen: Een Verhaal over Additieve Systemen

Stel je voor dat je een enorme, oneindige kast hebt vol met verschillende soorten legoblokken. Je wilt weten of je met deze specifieke verzameling blokken elk mogelijk getal (van de minste tot de oneindige plus) kunt bouwen, en dat je dat op één unieke manier kunt doen.

Dat is precies waar dit wetenschappelijke artikel over gaat. De auteur, Andrei Zabolotskii, onderzoekt een heel specifiek soort "lego-cassettes" voor de gehele getallenlijn (Z). Hij ontdekt dat het beantwoorden van de vraag "Kunnen we hiermee alles bouwen?" soms onmogelijk is om te weten, zelfs voor de slimste computers ter wereld.

Hier is de uitleg in simpele taal, met een paar creatieve vergelijkingen.

1. De Basis: Het Bouwsetje (Additieve Systemen)

In de wiskunde noemen ze dit een additief systeem.

Voorbeeld uit het dagelijks leven: Denk aan ons decimale getalstelsel (0-9). Je kunt elk getal maken door combinaties van 1, 10, 100, 1000, etc. te gebruiken. 538 is bijvoorbeeld 500 + 30 + 8. Dit werkt perfect voor positieve getallen.
Het probleem: Wat als je ook negatieve getallen wilt maken (zoals -5 of -100)? Dan wordt het veel lastiger. Je hebt speciale "legoblokken" nodig die je in de andere richting kunnen duwen.

De auteur introduceert een nieuw soort bouwsetje, die hij "canonieke verzamelingen" noemt. Dit zijn heel gestructureerde sets van getallen die erop lijken dat ze misschien elk getal kunnen vormen.

2. De Uitdaging: De "Gaten" in de Muur

Het grote raadsel is: Zijn deze specifieke sets echt compleet?
Stel je voor dat je een muur aan het bouwen bent. Je hebt een set bakstenen.

Als de set compleet is, kun je de muur tot in het oneindige aan beide kanten (links en rechts) volleggen zonder gaten.
Als de set niet compleet is, blijven er gaten over waar je geen steen in kunt leggen, hoe hard je ook probeert.

De vraag is: Hoe weet je, alleen maar door naar de lijst met bakstenen te kijken, of er gaten zullen ontstaan?

3. De Magische Bril: Van Wiskunde naar Spelletjes

De auteur doet iets heel slim. Hij kijkt niet meer naar de getallen als statische blokken, maar als een dynamisch spelletje. Hij verandert het probleem in een soort "rekenmachine" die een getal steeds opnieuw bewerkt.

De Analogie: Stel je voor dat elk getal een bal is die door een reeks glijbanen rolt.
- Als de bal uiteindelijk stilvalt op 0, dan is het getal "opgebouwd" en zit er geen gat in de muur.
- Als de bal blijft roteren of in een cirkel blijft draaien zonder te stoppen, dan is er een gat in de muur.

De vraag "Is dit systeem compleet?" wordt dan: "Stopt elke mogelijke bal ooit?"

4. De Twee Onoplosbare Monsters

Hier wordt het fascinerend. De auteur bewijst dat het bepalen of een systeem compleet is, precies hetzelfde is als het oplossen van twee beroemde, onmogelijke problemen:

Monster A: Het Collatz-gevaar (De 3n+1-uitdaging)

Er is een beroemd wiskundig raadsel genaamd de Collatz-voorspelling.

De regel: Neem een getal. Is het even? Deel door 2. Is het oneven? Vermenigvuldig met 3 en tel 1 op. Herhaal dit.
Het mysterie: Wiskundigen vermoeden dat je altijd uiteindelijk op 1 uitkomt, maar niemand kan het bewijzen.
De link: De auteur toont aan dat je een specifiek lego-setje kunt bouwen waarbij de vraag "Is dit setje compleet?" exact hetzelfde is als de vraag "Is de Collatz-voorspelling waar?". Als je het ene kunt oplossen, heb je het andere ook opgelost.

Monster B: Fractran (Het computer-spel)

Vervolgens kijkt hij naar Fractran, een vreemde programmeertaal bedacht door de wiskundige John Conway.

Het spel: Je hebt een getal en een lijst met breuken. Je vermenigvuldigt je getal met de eerste breuk die een heel getal oplevert. Herhaal dit.
Het probleem: Er is een bekend probleem: "Stopt dit programma altijd, voor elk startgetal?" Dit is een onbeslisbaar probleem. Dat betekent dat er geen algoritme bestaat dat dit voor elke mogelijke lijst van breuken kan voorspellen.
De link: De auteur toont aan dat je een lego-setje kunt maken dat precies werkt als een Fractran-programma. Als je wilt weten of je lego-setje perfect is (geen gaten), moet je weten of het Fractran-programma stopt. Omdat dat onmogelijk te weten is voor alle programma's, is het ook onmogelijk om te weten of alle lego-setjes compleet zijn.

5. De Conclusie: De Grenzen van de Wiskunde

De boodschap van dit artikel is diep en verrassend:

Het lijkt alsof we gewoon naar een lijst met getallen kijken en kunnen tellen of ze alles dekken. Maar de auteur bewijst dat voor bepaalde soorten sets, deze vraag fundamenteel onoplosbaar is.

Het is alsof je een doos met puzzelstukjes krijgt en je moet zeggen of ze de hele vloer kunnen bedekken. Soms is het antwoord niet "ja" of "nee", maar "we kunnen het nooit weten, omdat het antwoord gekoppeld is aan een mysterie dat de natuurwetten van de logica zelf uitdaagt."

Samengevat in één zin:
De auteur laat zien dat het controleren of een bepaalde verzameling getallen elk mogelijk getal kan vormen, net zo moeilijk is als het oplossen van het beroemde Collatz-raadsel of het voorspellen van het gedrag van een computerprogramma dat misschien wel, maar misschien ook nooit stopt – en dat laatste is wiskundig gezien onmogelijk.

Titel: Additieve systemen voor $\mathbb{Z}$ zijn onbeslisbaar

Auteur: Andrei Zabolotskii

1. Probleemstelling

Het artikel onderzoekt de fundamentele vraag in de additieve combinatoriek: welke verzamelingen van deelverzamelingen $A_i \subset \mathbb{Z}$ vormen een additief systeem voor de gehele getallen $\mathbb{Z}$ ?

Een verzameling $A = \{A_0, A_1, \dots\}$ is een additief systeem voor een monoid $M$ (hier $\mathbb{Z}$ ) als elke $n \in M$ op unieke wijze kan worden geschreven als een som $n = a_0 + a_1 + \dots$ , waarbij $a_i \in A_i$ en alle maar eindig veel $a_i$ gelijk zijn aan 0.

Hoewel dit probleem voor de niet-negatieve gehele getallen $\mathbb{N}_0$ volledig is opgelost door een stelling van de Bruijn (die aangeeft dat elk additief systeem voor $\mathbb{N}_0$ een contractie is van een "Brits getalsysteem"), is de situatie voor $\mathbb{Z}$ veel complexer en minder begrepen. De centrale vraag van dit paper is: Is het mogelijk om algorithmisch te bepalen of een gegeven verzameling een additief systeem voor $\mathbb{Z}$ is?

2. Methodologie

De auteur hanteert een tweeledige aanpak die additieve combinatoriek koppelt aan de theorie van dynamische systemen:

Definitie van "Canonieke Collecties":
De auteur introduceert een nieuwe klasse van verzamelingen, genaamd canonieke collecties. Deze generaliseren bekende systemen zoals het negabinaire systeem en het gebalanceerde ternaire systeem. Een canonieke collectie wordt gedefinieerd door twee sequenties:
- Een sequentie van basen $(b_i)_{i \in \mathbb{N}_0}$ met $b_i > 1$ .
- Een sequentie van verzamelingen $(T_i)_{i \in \mathbb{N}_0}$ , waarbij elke $T_i$ een volledig reststelsel modulo $b_i$ is dat 0 bevat.
  De verzamelingen in de collectie zijn van de vorm $A_i = (b_0 b_1 \dots b_{i-1}) T_i$ .
Vertaling naar Dynamische Systemen:
Het probleem van het bepalen of een getal $n \in \mathbb{Z}$ een unieke representatie heeft in een canonieke collectie, wordt vertaald naar het bestuderen van de trajectorie van $n$ onder een reeks afbeeldingen (maps) $f_i$ .
- Voor een getal $n$ wordt de volgende term in de rij berekend als $n_{i+1} = f_i(n_i) = \frac{1}{b_i}(n_i - t_i(n_i))$ , waarbij $t_i(n_i)$ het unieke element is in $T_i$ dat congruent is aan $n_i$ modulo $b_i$ .
- Een verzameling is een additief systeem (volledig) dan en slechts dan als de trajectorie van elk geheel getal $n$ uiteindelijk constant 0 wordt.

3. Belangrijkste Bijdragen en Resultaten

De kern van het paper bestaat uit twee hoofdstellingen die de complexiteit van het probleem aantonen door het te reduceren tot beroemde onoplosbare problemen:

Stelling 1: Equivalentie met de Collat-conjectuur

De auteur construeert een specifieke canonieke collectie $A_C$ zodanig dat:

$A_C$ een additief systeem voor $\mathbb{Z}$ is dan en slechts dan als de Collat-conjectuur waar is.
Mechanisme: De afbeeldingen $f_i$ in het bijbehorende dynamische systeem zijn zo ontworpen dat ze de iteraties van de Collat-functie ( $3n+1$ voor oneven, $n/2$ voor even) simuleren. Als de Collat-conjectuur waar is, bereikt elke trajectorie uiteindelijk 1 en vervolgens 0. Als er een tegenvoorbeeld bestaat, zal de trajectorie niet naar 0 convergeren, en is de collectie niet compleet.

Stelling 2: Onbeslisbaarheid via Fractran

De auteur introduceert een subklasse van canonieke collecties, genaamd Fractran-type collecties ( $A_F$ ), die gebaseerd zijn op het esoterische programmeertaal Fractran van John Conway.

Resultaat: Het probleem om te bepalen of een gegeven Fractran-type collectie $A_F$ compleet is, is onbeslisbaar (undecidable).
Redenering: Conway heeft aangetoond dat Fractran computationeel universeel is. De auteur toont aan dat het bepalen of een Fractran-programma voor alle invoer stopt (het universele halting-probleem voor Fractran), equivalent is aan het bepalen of de bijbehorende canonieke collectie een additief systeem vormt. Omdat het halting-probleem onbeslisbaar is, is ook het probleem voor deze additieve systemen onbeslisbaar.

4. Significatie en Conclusie

Fundamentele Grenzen: Het paper toont aan dat er geen algemene algoritme bestaat om te bepalen of een natuurlijke familie van verzamelingen (canonieke collecties) een additief systeem voor $\mathbb{Z}$ vormt. Dit is een scherp contrast met het geval van $\mathbb{N}_0$ , waar een volledige karakterisering bestaat (de Bruijn's stelling).
Verbinding van Velden: Het werk creëert een opmerkelijke brug tussen drie ogenschijnlijk verschillende gebieden:
1. Additieve combinatoriek (unieke representaties van getallen).
2. Getaltheorie en dynamische systemen (Collat-conjectuur).
3. Berekenbaarheidstheorie (onbeslisbaarheid en Fractran).
Nieuwe Inzichten: De resultaten suggereren dat de structuur van additieve systemen voor $\mathbb{Z}$ fundamenteel complexer is dan die voor $\mathbb{N}_0$ . Zelfs voor "goed gedragende" verzamelingen (zoals Fractran-types, die slechts eindige data vereisen om te specificeren), is de vraag naar volledigheid onoplosbaar.

Samenvattend bewijst Zabolotskii dat het karakteriseren van additieve systemen voor de gehele getallen niet alleen een moeilijk wiskundig probleem is, maar een probleem dat in zijn algemeenheid onoplosbaar is binnen de grenzen van de berekenbaarheid.