💻 computer science

On the Decidability of Monadic Theories of Arithmetic Predicates

Dit artikel onderzoekt de beslisbaarheid van monadische tweede-orde-theorieën over de natuurlijke getallen met specifieke rekenkundige predicaten, zoals machten en lineaire recurrente rijen, en levert nieuwe onvoorwaardelijke en voorwaardelijke beslisbaarheidsresultaten op door technieken uit dynamische systemen, getaltheorie en automata-theorie te combineren.

Oorspronkelijke auteurs: Valérie Berthé, Toghrul Karimov, Joris Nieuwveld, Joël Ouaknine, Mihir Vahanwala, James Worrell

Gepubliceerd 2026-03-25

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Valérie Berthé, Toghrul Karimov, Joris Nieuwveld, Joël Ouaknine, Mihir Vahanwala, James Worrell

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

Stel je voor dat je een gigantische, oneindige rij getallen hebt: 0, 1, 2, 3, 4, 5, ... Dit is de basis van onze wiskundige wereld. Nu, wat als we in deze rij bepaalde getallen "verfijnen" of "markeerren"? Bijvoorbeeld, we markeren alleen de even getallen, of alleen de machten van 2 (2, 4, 8, 16...), of de Fibonacci-getallen (1, 1, 2, 3, 5, 8...).

De vraag die deze wetenschappers zich stellen, is: Kunnen we een computer een "vraag" stellen over deze gemarkeerde rijen, zodat de computer altijd het juiste "ja" of "nee" antwoordt?

In de wiskundetaal noemen ze dit de "beslisbaarheid" van een theorie. Als het antwoord "ja" is, kunnen we een algoritme schrijven dat elke mogelijke vraag over deze getallen oplost. Als het antwoord "nee" is, is er geen manier om dit voor alle vragen te doen; de computer zou oneindig blijven nadenken of vastlopen.

Hier is een simpele uitleg van hun ontdekkingen, met een paar creatieve metaforen:

1. Het Grote Puzzelspel

Stel je voor dat je een enorme puzzel hebt. De stukjes zijn de getallen.

Simpel geval: Als je alleen kijkt naar de even getallen, is de puzzel makkelijk op te lossen. De computer kan dit prima.
Moeilijk geval: Wat als je kijkt naar de even getallen én de getallen die een macht van 3 zijn (3, 9, 27...)? En wat als je ze beide tegelijkertijd in de puzzel moet passen?

De auteurs ontdekten dat wanneer je twee verschillende soorten "patronen" (zoals machten van 2 en machten van 3) door elkaar haalt, het heel snel ingewikkeld wordt. Het is alsof je probeert twee verschillende muziekstijlen (jazz en klassiek) perfect op elkaar af te stemmen. Soms klinkt het geweldig, soms is het een chaos.

2. De "Tijdsreisklok" (Dynamische Systemen)

Hoe hebben ze dit opgelost? Ze keken niet naar de getallen als statische blokjes, maar als een bewegend systeem.

Stel je voor dat je een bal hebt die over een oneindig lang, rechthoekig tapijt rolt.

Het tapijt heeft lijnen erop getekend die de machten van 2 en 3 voorstellen.
De bal rolt met een bepaalde snelheid.
Elke keer als de bal een lijn raakt, tikt hij een klokje: "Bip! Ik heb een macht van 2 gezien!" of "Boep! Ik heb een macht van 3 gezien!"

De volgorde van die "bips" en "boeps" is de sleutel. De auteurs ontdekten dat als je de snelheid van de bal goed kiest (wat wiskundig te maken heeft met logaritmen), de bal een patroon volgt dat je kunt voorspellen. Ze gebruikten wiskundige regels (zoals de Schanuel-conjectuur, een soort "gok" van wiskundigen die ze als waar aannemen) om te zeggen: "Als deze bal zich zo gedraagt, dan kunnen we elke vraag over zijn route beantwoorden."

3. De Magische Spiegels (Getallen in andere talstelsels)

Een ander deel van hun onderzoek gaat over getallen die je schrijft in een ander systeem, zoals het binaire systeem (alleen 0 en 1) in plaats van ons gewone decimale systeem (0-9).

Stel je voor dat je een getal als $\sqrt{2}$ (de wortel uit 2) in binaire code schrijft: 0.10110101.... Dit lijkt op een willekeurig patroon van lichtjes die aan en uit gaan.

De auteurs ontdekten dat als je kijkt naar de getallen die een macht van 2 zijn én de getallen die een kwadraat zijn (zoals 4, 9, 16), dit precies hetzelfde patroon is als die magische lichtjes van $\sqrt{2}$ .
Als we aannemen dat die lichtjes van $\sqrt{2}$ echt willekeurig zijn (een theorie die "normaal getal" heet), dan kunnen we ook vragen beantwoorden over de machten en kwadraten.

4. De Belangrijkste Ontdekkingen (De "Winst")

De wetenschappers hebben een lijstje gemaakt van situaties waar de computer wél het antwoord kan geven:

Ja: De theorie van "machten van 2" én "Fibonacci-getallen" is oplosbaar.
Ja: De theorie van "machten van 2", "machten van 3" en "machten van 6" is oplosbaar.
Ja (als we geloven in een wiskundige gok): De theorie van "machten van 2", "machten van 3" en "machten van 5" is oplosbaar, mits we aannemen dat bepaalde getallen (zoals logaritmen) geen verborgen verbanden hebben (de Schanuel-conjectuur).
Ja: De theorie van "machten van 4" en "kwadraten" is oplosbaar.

Waarom is dit belangrijk?

Vroeger dachten wiskundigen dat zodra je twee complexe patronen (zoals priemgetallen of machten) combineerde, de computer het nooit meer zou kunnen oplossen. Deze paper zegt: "Niet altijd!"

Ze hebben laten zien dat als je de patronen op de juiste manier bekijkt (als een bewegende bal op een tapijt of als een lichtpatroon in een spiegel), de chaos een orde krijgt die een computer wel kan begrijpen. Ze hebben een brug gebouwd tussen de wereld van de getallen, de wereld van de computers en de wereld van de beweging (dynamische systemen).

Kortom: Ze hebben bewezen dat voor bepaalde, specifieke combinaties van getallenpatronen, de "grote puzzel" oplosbaar is, zolang we maar de juiste bril opzetten om naar de beweging van de getallen te kijken.

Titel: Over de Beslisbaarheid van Monadische Theorieën van Aritmetische Predikaten

Auteurs: Valérie Berthé, Toghrul Karimov, Joris Nieuwveld, Joël Ouaknine, Mihir Vahanwala, en James Worrell.

1. Het Probleem

Het artikel onderzoekt de beslisbaarheid van de monadische tweede-orde (MSO) theorie van structuren van de vorm $\langle \mathbb{N}; <, P_1, \dots, P_d \rangle$ , waarbij $\mathbb{N}$ de natuurlijke getallen zijn, $<$ de standaard orde is, en $P_1, \dots, P_d$ unaire predikaten (verzamelingen van natuurlijke getallen) zijn.

Achtergrond: De MSO-theorie van $\langle \mathbb{N}; < \rangle$ alleen is bekend als beslisbaar (Büchi, 1962). De uitdaging ligt bij het uitbreiden van deze structuur met specifieke predikaten. Voor sommige predikaten (zoals de priemgetallen) is beslisbaarheid een open probleem of zelfs onmogelijk (onder bepaalde conjectures).
Focus: De auteurs richten zich op "aritmatische predikaten" die voortkomen uit de studie van lineaire recurrente rijen (LRS). Specifieke voorbeelden zijn:
- Vaste-basis machten: $k^\mathbb{N} = \{k^n : n \in \mathbb{N}\}$ .
- $k$ -de machten: $\mathbb{N}^k = \{n^k : n \in \mathbb{N}\}$ .
- De rij van Fibonacci-getallen en andere LRS met één niet-herhaalde dominante wortel.
Kernvraag: Voor welke combinaties van dergelijke predikaten is de MSO-theorie van de uitbreiding beslisbaar? Vooral de interactie tussen meerdere predikaten (bijv. $\langle \mathbb{N}; <, 2^\mathbb{N}, 3^\mathbb{N} \rangle$ ) is complex en eerder onopgelost.

2. Methodologie

De auteurs combineren technieken uit drie domeinen: automatentheorie, getaltheorie en dynamische systemen. Hun aanpak volgt een gestructureerd proces:

Reductie naar Automata Acceptatie:
- Gegeven een MSO-formule $\varphi$ , construeren ze een automaat $A$ die de karakteristieke woord $\alpha$ van de structuur accepteert als en slechts als $\varphi$ waar is. Het karakteristieke woord encodeert voor elke positie $n$ welke predikaten $n$ bevatten.
- Het beslisbaarheidsprobleem is Turing-equivalent aan het probleem of een automaat een oneindig woord accepteert ( $Acc_\alpha$ ).
Compressie tot "Order Words":
- In plaats van het volledige karakteristieke woord te analyseren, reduceren ze het probleem naar het order woord ( $\beta$ ). Dit woord bevat alleen de volgorde waarin de elementen van de predikaten $P_1, \dots, P_d$ voorkomen, zonder de tussenliggende nullen.
- Ze bewijzen dat voor "effectief procyclische" en "effectief schaarse" predikaten, de acceptatie van het karakteristieke woord Turing-equivalent is aan de acceptatie van het order woord.
Dynamische Systemen Modellering:
- Voor LRS met één dominante wortel: De volgorde van de termen wordt gemodelleerd door translaties op een $d$ -dimensionale torus $\mathbb{T}^d$ (d.w.z. $x \mapsto x + t \pmod 1$ ). Dit leidt tot snijsequenties (cutting sequences) of billiard words.
- Voor mengsels van machten en polynomen: Ze gebruiken dynamische systemen van de vorm $x \mapsto \{b \cdot x\}$ (waarbij $\{ \cdot \}$ het fractionele deel is), wat correspondeert met de expansie van getallen in een gehele basis $b$ .
Beslisbaarheid via Eigenschappen:
- Ze gebruiken eigenschappen van deze dynamische systemen (zoals uniforme recurrentie en factor complexiteit) om te bepalen of een automaat het woord accepteert.
- Ze maken gebruik van diepe resultaten uit de getaltheorie, zoals Baker's stelling (over lineaire vormen in logaritmen) en Schanuel's conjectuur (over transcendentie).

3. Belangrijkste Bijdragen en Resultaten

De paper levert zowel onvoorwaardelijke als voorwaardelijke beslisbaarheidsresultaten:

A. Onvoorwaardelijke Resultaten (zonder extra conjectures)

Meerdere machten met onafhankelijke logaritmen: De MSO-theorie van $\langle \mathbb{N}; <, P_1, \dots, P_d \rangle$ $⟨ N; <, P_{1}, \dots, P_{d} ⟩$ is beslisbaar als $P_i = \{a_i \rho_i^n\}$ $P_{i} = {a_{i} ρ_{i}^{n}}$ en de getallen $1/\log(\rho_1), \dots, 1/\log(\rho_d)$ $1/ lo g (ρ_{1}), \dots, 1/ lo g (ρ_{d})$ lineair onafhankelijk zijn over $\mathbb{Q}$ $Q$ .
- Voorbeeld: De theorie van $\langle \mathbb{N}; <, 2^\mathbb{N}, 3^\mathbb{N} \rangle$ is beslisbaar.
- Voorbeeld: De theorie van $\langle \mathbb{N}; <, 2^\mathbb{N}, 3^\mathbb{N}, 6^\mathbb{N} \rangle$ is beslisbaar (hoewel de logaritmen hier lineair afhankelijk zijn, voldoet de specifieke structuur aan de voorwaarden).
Machten en Fibonacci: De MSO-theorie van $\langle \mathbb{N}; <, 2^\mathbb{N}, \text{Fib} \rangle$ is beslisbaar.
Machten en $k$ -de machten: De MSO-theorie van $\langle \mathbb{N}; <, 4^\mathbb{N}, \mathbb{N}^2 \rangle$ is beslisbaar.

B. Voorwaardelijke Resultaten (onder Schanuel's Conjectuur)

Algemene machten: Als men Schanuel's conjectuur aanneemt (een fundamentele conjectuur in de transcendentgetaltheorie), dan is de MSO-theorie van $\langle \mathbb{N}; <, P_1, \dots, P_d \rangle$ $⟨ N; <, P_{1}, \dots, P_{d} ⟩$ beslisbaar voor elke verzameling van machten $P_i = \{a_i \rho_i^n\}$ $P_{i} = {a_{i} ρ_{i}^{n}}$ , zelfs als de logaritmen lineair afhankelijk zijn.
- Voorbeeld: De theorie van $\langle \mathbb{N}; <, 2^\mathbb{N}, 3^\mathbb{N}, 5^\mathbb{N} \rangle$ is beslisbaar onder deze aanname.
Opmerking: De algoritmen zijn zo ontworpen dat ze alleen afhankelijk zijn van de conjectuur voor terminatie. Als het algoritme stopt, is het antwoord onvoorwaardelijk correct.

C. Resultaten gerelateerd aan Expansies in Hele Bases

Verbinding met Irrationale Getallen: Voor structuren zoals $\langle \mathbb{N}; <, \mathbb{N}^2, 2^\mathbb{N} \rangle$ (kwadraten en machten van 2), tonen de auteurs aan dat de MSO-theorie Turing-equivalent is aan de MSO-theorie van de binaire expansie van $\sqrt{2}-1$ .
Normaliteit: Als de binaire expansie van $\sqrt{2}-1$ disjunctief is (wat volgt uit de conjectuur dat $\sqrt{2}$ een normaal getal is), dan is de MSO-theorie beslisbaar. Dit koppelt een logisch probleem direct aan een open vraag in de getaltheorie.

D. Niet-uniforme Beslisbaarheid

Voor een vast gegeven stel parameters (bijv. vaste $a_i, \rho_i$ ) bestaat er een algoritme dat de MSO-theorie beslist, zelfs als de lineaire onafhankelijkheid niet bewezen is. Het algoritme "kent" echter de ideale relatie tussen de logaritmen (een niet-uniforme eigenschap).

4. Significantie en Impact

Overbrugging van Domeinen: Het artikel is een voorbeeld van hoe problemen uit de wiskundige logica (beslisbaarheid) kunnen worden opgelost door technieken uit dynamische systemen (torus-translaties, snijsequenties) en getaltheorie (Baker's stelling) te combineren.
Oplossing van Open Problemen: Het levert de eerste onvoorwaardelijke bewijzen voor de beslisbaarheid van de MSO-theorie van structuren met meerdere interactieve aritmatische predikaten (zoals $\langle \mathbb{N}; <, 2^\mathbb{N}, 3^\mathbb{N} \rangle$ ), wat decennia een open probleem was.
Koppeling aan Fundamentele Conjectures: De auteurs tonen aan dat de beslisbaarheid van bepaalde MSO-theorieën equivalent is aan diepe onopgeloste problemen in de getaltheorie (zoals de normaliteit van algebraïsche getallen of Schanuel's conjectuur). Dit geeft een nieuwe context aan deze conjectures.
Technische Innovatie: De introductie van het concept van "order words" en de reductie naar dynamische systemen biedt een nieuwe methodologische toolbox voor het analyseren van complexe interacties tussen predikaten, verder dan de traditionele "contraction method" van Elgot en Rabin.

Samenvattend biedt dit artikel een grondig kader voor het begrijpen van de grenzen van de beslisbaarheid in de logica van natuurlijke getallen met aritmische uitbreidingen, en plaatst deze grenzen scherp in het licht van de moderne getaltheorie.