🔢 mathematics

On the Diophantine problem related to power circuits

Dit artikel bewijst dat het Diophantische probleem voor de structuur $\langle \mathbb{N}_{>0}; +, x \cdot 2^y, \leq, 1 \rangle$ , die nauw verwant is aan machtskringen, onbeslisbaar is.

Oorspronkelijke auteurs: Alexander Rybalov

Gepubliceerd 2026-03-20

📖 4 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Alexander Rybalov

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 Wiskundige Puzzel die Niemand Kan Oplossen: Een Verhaal over "Krachtige Schakelingen"

Stel je voor dat wiskunde een gigantisch legpuzzel is. Sommige puzzels zijn makkelijk: je kunt ze oplossen door gewoon te tellen of te delen. Andere puzzels zijn zo ingewikkeld dat ze lijken op een doolhof zonder uitgang.

Dit artikel gaat over een specifieke puzzel die wiskundigen Myasnikov, Ushakov en Won in 2012 hebben bedacht. Ze noemden hun gereedschap "Power Circuits" (Krachtige Schakelingen).

1. Wat zijn deze "Krachtige Schakelingen"?

Stel je een rekenmachine voor die niet alleen kan optellen, maar ook een magische knop heeft.

Normale rekenmachine: $5 + 3 = 8$ .
Deze magische machine: Als je twee getallen hebt, zeg $x$ en $y$ , kan hij ze vermenigvuldigen met een macht van twee. De formule is: $x \cdot 2^y$ .

Dit klinkt misschien niet zo spannend, maar het is een superkracht. Met deze machine konden de oorspronkelijke onderzoekers een heel moeilijke puzzel oplossen (het "woordprobleem" in de Baumslag-groep) die normaal gesproken eeuwen zou duren. Ze deden dit in een fractie van een seconde.

2. De Grote Vraag: Kunnen we alles hiermee oplossen?

De onderzoekers vroegen zich af: "Als we deze magische machine hebben, kunnen we dan elke wiskundige vergelijking oplossen die we erin stoppen?"

In de wiskunde noemen we dit het Diophantische probleem. Het is als het proberen te vinden van de juiste sleutel voor een slot.

Als je een slot hebt met een simpele sleutel (alleen optellen en vermenigvuldigen), weten we al lang dat er geen algemene sleutel bestaat die elk slot opent (dit is het beroemde Tiende Probleem van Hilbert, opgelost door Matiyasevich).
Maar deze nieuwe machine is slimmer. Misschien is hij slim genoeg om wel een oplossing te vinden voor alles?

De auteur van dit artikel, Alexander Rybalov, zegt: "Nee, dat is hij niet."

3. Het Bewijs: De "Magische" Vermenigvuldiging

Rybalov toont aan dat je met deze "Krachtige Schakelingen" eigenlijk alles kunt doen wat je met gewone vermenigvuldiging kunt doen.

Hoe doet hij dat? Hij gebruikt een slimme truc, alsof hij een magische sleutel nabootst:

Deelbaarheid: Hij laat zien dat je kunt controleren of één getal een ander getal deelt (bijvoorbeeld: gaat 3 in 12 op?) door alleen de magische knop te gebruiken.
De Logaritme: Hij laat zien dat je kunt tellen hoe vaak je moet verdubbelen om bij een getal te komen (zoals het tellen van trappen in een trap).
Het Kwadraat: Hij toont aan dat je een getal met zichzelf kunt vermenigvuldigen ( $x \cdot x$ ).
De Grote Vermenigvuldiging: Als je kunt kwadrateren en optellen, kun je ook twee willekeurige getallen vermenigvuldigen ( $x \cdot y$ ).

De Metafoor:
Stel je voor dat je een gereedschapskist hebt met alleen een hamer en een schroevendraaier. Je denkt: "Kan ik hiermee een auto repareren?"
Rybalov bewijst dat je met die hamer en schroevendraaier eigenlijk een complete autowerkplaats kunt bouwen. Je kunt er een motor uit elkaar halen, wielen vervangen en alles wat een echte garage kan doen.

Omdat we al weten dat het oplossen van alle wiskundige vergelijkingen met gewone vermenigvuldiging onmogelijk is (er is geen algoritme dat altijd werkt), betekent dit dat het ook onmogelijk is met deze "Krachtige Schakelingen".

4. Het Resultaat: Een Doelwit dat Onbereikbaar is

Rybalov concludeert: Het Diophantische probleem voor deze structuur is onbeslisbaar.

Wat betekent dat in het dagelijks leven?
Het betekent dat er een computerprogramma bestaat dat nooit zal kunnen zeggen of een bepaalde vergelijking met deze magische getallen een oplossing heeft of niet. Je kunt het proberen, maar de computer zal voor altijd blijven rekenen of vastlopen. Er is geen "antwoordknop" die altijd werkt.

5. Een Bijkomend Geheim: Is het "Automatisch"?

In het artikel wordt ook een andere vraag beantwoord: "Is deze structuur 'automatisch'?"
In de wiskunde betekent "automatisch" dat een computer de structuur heel makkelijk en snel kan begrijpen, alsof het een simpele robot is die alleen reageert op vaste regels.

Rybalov zegt: "Nee, dit is geen simpele robot."
Omdat het probleem zo complex is (onoplosbaar), is de structuur te ingewikkeld om "automatisch" te zijn. Het is meer als een menselijke genie dat soms raar doet en niet altijd voorspelbaar is.

Samenvatting in één zin

Alexander Rybalov bewijst dat de slimme wiskundige "Krachtige Schakelingen", die ooit werden bedacht om een heel moeilijk probleem snel op te lossen, uiteindelijk toch niet slim genoeg zijn om elke wiskundige vergelijking op te lossen; het blijft een mysterie dat voor computers onoplosbaar is.

Titel: Over het Diophantische Probleem gerelateerd aan Power Circuits

Auteur: Alexander Rybalov (Sobolev Institute of Mathematics, Rusland)
Publicatiedatum: 19 maart 2026 (arXiv)

1. Het Probleem

Het artikel adresseert een fundamentele vraag in de rekenbare theorie en de algebraïsche structuren: de beslisbaarheid van het Diophantische probleem over een specifieke rekenkundige structuur.

De Structuur: De auteur onderzoekt de structuur $\tilde{\mathbb{N}} = \langle \mathbb{N}_{>0}; +, x \cdot 2^y, \le, 1 \rangle$ . Hierbij is $\mathbb{N}_{>0}$ de verzameling van natuurlijke getallen groter dan 0. De operaties zijn optelling ( $+$ ), de "power circuit" operatie $(x, y) \mapsto x \cdot 2^y$ , de orde-relatie ( $\le$ ) en het getal 1.
De Context: Power circuits zijn computatiestructuren geïntroduceerd door Myasnikov, Ushakov en Won (2012) om een polynomiale tijdscomplexiteit-algoritme te construeren voor het woordprobleem in de Baumslag-groep $G(1,2)$ . Deze groep heeft een niet-elementaire Dehn-functie.
De Vraag: Myasnikov, Ushakov en Won stelden in [7, Probleem 10.3] de vraag of het Diophantische probleem over $\tilde{\mathbb{N}}$ beslisbaar (decidable) is. Het Diophantische probleem vraagt of er een algoritme bestaat dat voor elke gegeven vergelijking (of stelsel vergelijkingen) over deze structuur kan bepalen of er een oplossing bestaat in $\mathbb{N}_{>0}$ .

2. Methodologie

Rybalov bewijst dat het probleem onbeslisbaar is door een reductie te gebruiken van een reeds bekend onbeslisbaar probleem. De aanpak bestaat uit de volgende stappen:

Reductie van het klassieke Diophantische probleem:
De auteur toont eerst aan dat het Diophantische probleem over $\mathbb{N}_{>k}$ (natuurlijke getallen groter dan $k$ ) onbeslisbaar is voor elke $k$ . Dit wordt gedaan via een Cook/Turing-reductie van het klassieke Hilbert-tiende probleem (over $\mathbb{N}$ ) naar $\mathbb{N}_{>k}$ . Omdat het klassieke probleem onbeslisbaar is (Matiyasevich), is dat van $\mathbb{N}_{>k}$ dat ook.
Diophantische Definieerbaarheid in $\tilde{\mathbb{N}}$ :
Om het probleem over $\mathbb{N}_{>1}$ te reduceren naar $\tilde{\mathbb{N}}$ , moet de auteur aantonen dat de basisoperaties van de vermenigvuldiging en de orde binnen $\tilde{\mathbb{N}}$ Diophantisch definieerbaar zijn. Een relatie of functie is Diophantisch definieerbaar als deze kan worden uitgedrukt als een existentiële kwantificatie van een stelsel vergelijkingen over de basisoperaties van de structuur.

De auteur bewijst de volgende definieerbaarheden:
- Deelbaarheid ( $x|y$ ): Gebruikmakend van de eigenschap $m|n \iff 2^m-1 | 2^n-1$ . Omdat $2^x-1$ kan worden uitgedrukt via de operatie $x \cdot 2^y$ (specifiek $1 \cdot 2^x - 1$ ), kan deelbaarheid worden gedefinieerd.
- Strikte Orde ( $x < y$ ): Gedefinieerd via $x < y \iff \exists z (x + z = y)$ .
- Gehele Logaritme ( $\lfloor \log_2 x \rfloor$ ): Gedefinieerd via de ongelijkheden $2^y \le x < 2^{y+1}$ .
- Kwadrateren ( $sq(x) = x^2$ ): Dit is de meest complexe stap. De auteur construeert een Diophantische verzameling die elementen bevat van de vorm $kx(x+1)$. Door een combinatie van deelbaarheidsvoorwaarden en een beperking op de logaritme (om de grootte te beperken), wordt bewezen dat alleen $x^2$ (en geen andere kandidaten zoals $2x^2+x$ ) voldoet aan een specifiek stelsel voorwaarden.
- Vermenigvuldiging ($mul(x, y) = xy$): Gebruikmakend van de identiteit $z = xy \iff 2z = (x+y)^2 - x^2 - y^2$ . Omdat optelling en kwadrateren Diophantisch definieerbaar zijn, volgt hieruit dat vermenigvuldiging ook definieerbaar is.
De Reductie:
Elk stelsel Diophantische vergelijkingen over $\mathbb{N}_{>1}$ kan worden omgezet in een equivalent stelsel over $\tilde{\mathbb{N}}$ door de basisoperaties ( $+$ en $\cdot$ ) te vervangen door hun Diophantische definities in $\tilde{\mathbb{N}}$ .

3. Belangrijkste Bijdragen en Resultaten

Hoofdstelling (Theorem 2.9): Het Diophantische probleem over de structuur $\tilde{\mathbb{N}} = \langle \mathbb{N}_{>0}; +, x \cdot 2^y, \le, 1 \rangle$ is onbeslisbaar.
Constructie van Vermenigvuldiging: Een cruciaal technisch resultaat is de constructieve bewijsvoering dat vermenigvuldiging van getallen groter dan 1 Diophantisch definieerbaar is binnen een structuur die alleen optelling en de "power" operatie ( $x \cdot 2^y$ ) als basis heeft.
Negatief antwoord op een open vraag: De stelling beantwoordt negatief de vraag of $\tilde{\mathbb{N}}$ $\tilde{N}$ een automatische structuur is (Probleem 10.5 in [7]).
- Redenering: Elke automatische structuur heeft een beslisbare eerste-orde theorie (en dus een beslisbaar Diophantisch probleem). Omdat het Diophantische probleem over $\tilde{\mathbb{N}}$ onbeslisbaar is, kan $\tilde{\mathbb{N}}$ geen automatische structuur zijn.

4. Betekenis en Implicaties

Beperkingen van Power Circuits: Hoewel power circuits zeer efficiënt zijn voor het oplossen van het woordprobleem in specifieke groepen (zoals de Baumslag-groep), blijkt de onderliggende rekenkundige structuur te krachtig te zijn om een volledig Diophantisch probleem te bevatten. Dit betekent dat er geen algoritme bestaat dat voor elk stelsel vergelijkingen in deze structuur kan bepalen of een oplossing bestaat.
Relatie met andere Structuren: Het resultaat plaatst $\tilde{\mathbb{N}}$ $\tilde{N}$ in een interessante positie tussen bekende structuren:
- Het is onbeslisbaar (in tegenstelling tot $\langle \mathbb{N}; +, x \mapsto 2^x \rangle$ , waarvan Semenov bewees dat de theorie beslisbaar is).
- Het is onbeslisbaar ondanks dat de basisoperaties beperkt lijken (geen directe vermenigvuldiging), omdat de interactie tussen optelling en de machtsoperatie voldoende complexiteit genereert om vermenigvuldiging te simuleren.
Theoretische Implicatie: Het werk illustreert hoe de toevoeging van de operatie $(x, y) \mapsto x \cdot 2^y$ aan de standaard optelling, in combinatie met de orde, de expressiviteit van de structuur verhoogt tot het punt van onbeslisbaarheid, zelfs zonder expliciete vermenigvuldiging als basisoperatie.

Conclusie: Alexander Rybalov heeft bewezen dat het Diophantische probleem over power circuits onbeslisbaar is. Dit lost een langdurige open vraag op en bevestigt dat de structuur $\tilde{\mathbb{N}}$ niet automatische eigenschappen bezit, wat belangrijke gevolgen heeft voor de theoretische informatica en de groepentheorie.