🔢 mathematics

Shannon meets Gödel-Tarski-Löb: Undecidability of Shannon Feedback Capacity for Finite-State Channels

Dit artikel bewijst dat het exacte beslissingsprobleem voor de feedbackcapaciteit van eindig-toestandskanalen onbeslisbaar is, wat impliceert dat er geen algoritme bestaat om deze capaciteit voor alle gevallen exact te bepalen en dat dit probleem buiten het bestaande theorema van de reële getallen valt.

Oorspronkelijke auteurs: Angshul Majumdar

Gepubliceerd 2026-03-19

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Angshul Majumdar

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 communicatie-expert bent die probeert te begrijpen hoe snel een boodschap door een heel complex, geheugenrijk systeem kan reizen. Denk aan een oude telefoonlijn met veel ruis, of een netwerk van brievenbussen die hun inhoud onthouden. In de wereld van de communicatiewetenschap noemen we dit een "kanaal met geheugen".

De vraag die deze paper beantwoordt, is heel simpel: "Is het mogelijk om een perfecte, onfeilbare computer te bouwen die voor elk mogelijk kanaal exact kan berekenen wat de maximale snelheid is?"

Het antwoord van de auteur, Angshul Majumdar, is een verrassend en fundamenteel "Nee".

Hier is de uitleg, vertaald naar alledaagse taal met een paar creatieve vergelijkingen:

1. Het Probleem: De "Perfecte Voorspeller"

Stel je voor dat je een machine hebt die een kanaal bekijkt en zegt: "Ja, dit kanaal kan 100 bits per seconde aan" of "Nee, de limiet is 99,9 bits".
De auteurs kijken naar een specifieke, vrij simpele soort kanaal:

Het werkt met alleen 0-en en 1-en (zoals een lichtschakelaar).
Het heeft een "geheugen" (een staat), maar dat geheugen is eindig (zoals een klein rekentoestel).
De regels zijn strikt wiskundig en logisch (geen willekeurige irrationale getallen).

Je zou denken: "Als het systeem zo simpel en logisch is, moet een computer het toch kunnen uitrekenen?"

2. De Ontdekking: De "Onzichtbare Muur"

De paper bewijst dat er een fundamentele muur bestaat. Zelfs voor deze simpele, logische systemen is het onmogelijk om een algoritme te schrijven dat voor elke mogelijke instelling exact kan zeggen of de snelheid boven of onder een bepaalde drempel ligt.

De Analogie van de "Trage Boodschapper":
Stel je voor dat je twee soorten brievenbussen hebt:

Bus A (De "Goede"): De eerste 100 brieven worden gewoon opgevangen, maar daarna begint de bus plotseling perfect te werken en elke brief direct door te sturen.
Bus B (De "Slechte"): De eerste 100 brieven worden ook opgevangen, maar daarna blijft de bus voor altijd stil (of werkt hij volledig willekeurig).

Als je alleen kijkt naar de eerste 100 brieven, zien beide bussen er exact hetzelfde uit. Je kunt ze niet onderscheiden.

Als je wacht tot de 101e brief, zie je het verschil.
Maar wat als de "wachtperiode" 1 miljard brieven duurt? Of 1 googol?

De paper bewijst dat je nooit zeker kunt weten of je moet wachten tot die ene moment waarop het kanaal "opstart" of niet. Omdat je niet weet hoe lang je moet wachten, kun je nooit een eindig algoritme maken dat voor elk kanaal het antwoord geeft. Het is alsof je probeert te voorspellen of een onzichtbare muis ooit een muisval zal indrukken, terwijl de muis misschien pas over een miljoen jaar wakker wordt.

3. De Grootte van het Probleem: "Godel, Tarski en Lob"

De titel van de paper noemt drie beroemde logici: Gödel, Tarski en Löb. Waarom?
Omdat dit probleem niet alleen een technisch probleem is, maar een logisch fundamenteel probleem.

Gödel leerde ons dat er in elk complex genoeg wiskundig systeem waarheden zijn die je nooit kunt bewijzen.
Tarski leerde ons dat je de "waarheid" van een systeem niet volledig binnen datzelfde systeem kunt definiëren.
Löb gaf regels over wat een systeem over zichzelf kan zeggen.

De auteurs zeggen: "Omdat we kunnen bewijzen dat het berekenen van deze snelheid onmogelijk is voor een computer, betekent dit ook dat er geen 'perfecte wiskundige theorie' bestaat die alle antwoorden kan geven."
Het is alsof je een taal probeert te leren die zo complex is dat je nooit een woordenboek kunt maken dat elk woord in die taal definitieert. Er zullen altijd zinnen zijn die waar zijn, maar die je nooit kunt bewijzen met de regels van die taal.

4. Wat betekent dit voor de praktijk? (Is het een ramp?)

Nee, helemaal niet. De paper is niet pessimistisch, maar realistisch.

Het is geen einde van de wetenschap: Voor veel specifieke, goed gestructureerde kanalen (zoals die in je telefoon of internet) hebben we al lang goede formules en methodes. Die werken prima.
Het is een grens: De paper zegt: "Je kunt niet één 'super-algoritme' maken dat voor elk denkbaar kanaal werkt."
De oplossing: In plaats van te zoeken naar een universele oplossing, moeten wetenschappers zich blijven focussen op specifieke gevallen. Als je weet dat een kanaal een bepaalde structuur heeft (bijvoorbeeld dat het snel "opwarmt" of een bepaald patroon volgt), dan kun je wel een oplossing vinden.

Samenvatting in één zin

Deze paper bewijst dat er een fundamentele grens is aan wat we wiskundig kunnen berekenen over de snelheid van communicatie: voor de meest algemene, simpele systemen is het onmogelijk om een perfecte voorspeller te bouwen, en dat is een eigenschap van de logica zelf, niet van onze huidige technologie.

Het is een herinnering dat de natuur (en de wiskunde) soms dieper is dan onze rekenmachines, en dat we onze energie beter kunnen steken in het begrijpen van specifieke patronen dan in het zoeken naar een universele sleutel die niet bestaat.

Titel en Kernvraag

Titel: Shannon ontmoet Gödel-Tarski-Löb: Onbeslisbaarheid van de Shannon-feedbackcapaciteit voor kanaal met eindige toestanden.
Kernvraag: Is het mogelijk om een algoritme te construeren dat voor een willekeurig kanaal met eindige toestanden (Finite-State Channel, FSC) met feedback en een rationele drempelwaarde $q$ , exact kan beslissen of de feedbackcapaciteit $C_{fb}$ groter dan of gelijk aan $q$ is?

1. Probleemdefinitie en Context

Het artikel onderzoekt het exacte beslissingsprobleem voor de feedbackcapaciteit van kanaalmodellen met geheugen.

Input: Een effectieve codering $e$ van een binair invoer/binair uitvoer, rationeel geparametriseerd, unifilar kanaal met eindige toestanden ( $W_e$ ), een specifieke rationele initiële toestandsverdeling ( $\pi_{1,e}$ ), en een rationele drempelwaarde $q \in \mathbb{Q}$ .
Vraag: Geldt $C_{fb}(W_e, \pi_{1,e}) \geq q$ ?
Aandachtspunt: De focus ligt strikt op exactheid en de oneindige horizon. Het artikel behandelt geen benaderingsproblemen, geen eindige-horizon-subsituten en geen "promise-gap" varianten.

Historische Context:
Hoewel er veel succesvolle theorieën bestaan voor gestructureerde subclasses van FSC's (bijv. via dynamische programmering of single-letter karakteriseringen), blijft de exacte feedbackcapaciteit voor de algemene klasse van kanaalmodellen met geheugen intrinsiek asymptotisch en structureel delicaat. De vraag was of er een universele exacte beslissingsprocedure bestaat voor een breed, effectief gespecificeerd klasse van FSC's.

2. Methodologie en Constructie

De auteur gebruikt een combinatie van informatietheorie, berekenbaarheidstheorie en wiskundige logica om een onmogelijkheidsresultaat te bewijzen.

A. De Kanaalklasse

Het bewijs richt zich op een zeer beperkte klasse van kanaalmodellen:

Binair invoer en binair uitvoer.
Eindige toestandsruimte.
Rationale parameters (overgangs- en uitvoerkansen).
Unifilar: De volgende toestand wordt deterministisch bepaald door de huidige toestand, invoer en uitvoer ( $S_{t+1} = f(S_t, X_t, Y_t)$ ).

B. De "Delayed-Activation" Constructie

De kern van het bewijs is een specifieke constructie van twee families van kanaalmodellen, $Ch(N)_{good}$ en $Ch(N)_{bad}$ , die afhankelijk zijn van een parameter $N$ :

Vertragingsfase: Voor de eerste $N+1$ tijdstappen gedragen beide kanalen zich identiek. De uitvoer is deterministisch 0, ongeacht de invoer. De informatiestroom is in deze fase 0.
Actieve fase: Na $N+1$ $N + 1$ stappen komt het kanaal in een "absorberende" toestand ( $\star$ $⋆$ ).
- Bij $Ch(N)_{good}$ is het kanaal in deze fase een ruisvrij kanaal (uitvoer = invoer). De capaciteit is 1.
- Bij $Ch(N)_{bad}$ is het kanaal in deze fase volledig ruisbeïnvloed (uitvoer is onafhankelijk van invoer). De capaciteit is 0.

Cruciaal punt: Voor elke eindige horizon $n \leq N+1$ zijn de geoptimaliseerde waarden van de gerichte informatie ( $V_n$ ) voor beide kanalen exact gelijk (namelijk 0). Echter, de asymptotische feedbackcapaciteit ( $C_{fb}$ ) is fundamenteel verschillend (1 vs 0).

C. Reductie naar een Onbeslisbaar Probleem

De auteur voert een veel-een-reductie (many-one reduction) uit vanuit een bekend onbeslisbaar probleem (zoals het Halting-probleem of een equivalent) naar het feedbackcapaciteitsdrempelprobleem.

Er wordt een computeerbare functie geconstrueerd die een instantie van het onbeslisbare probleem mapt naar een kanaal $W_e$ en een drempel $q$ .
Als er een algoritme zou bestaan om $C_{fb} \geq q$ te beslissen, zou dit leiden tot een oplossing voor het onbeslisbare probleem, wat een contradictie is.

3. Belangrijkste Resultaten en Bijdragen

Het artikel levert vier fundamentele bijdragen:

Onbeslisbaarheid van Exacte Drempelwaarde:
Het bewijs dat het predikaat $Cap(e, q)$ (is $C_{fb} \geq q$ ?) onbeslisbaar is, zelfs voor de streng beperkte klasse van rationele, unifilar, binair FSC's. Er bestaat geen algoritme dat dit probleem voor alle instanties in deze klasse correct oplost.
Barrière voor Real-Algebraïsche Formuleringen ( $\exists\mathbb{R}$ ):
Het artikel toont aan dat de taal van exacte drempelwaarden ( $L_{Cap}$ ) niet behoort tot de complexiteitsklasse $\exists\mathbb{R}$ (de existentiële theorie van de reële getallen).
- Dit betekent dat het probleem niet kan worden gereduceerd tot een eindig stelsel van polynoomvergelijkingen en -ongelijkheden over de reële getallen.
- Aangezien $\exists\mathbb{R}$ -problemen beslisbaar zijn (in PSPACE), bevestigt dit dat het feedbackcapaciteitsprobleem fundamenteel complexer is dan standaard algebraïsche beslissingsproblemen.
Onmogelijkheid van Uniforme Karakteriseringen:
Er bestaat geen uniforme "finite-letter" (eindige-brieven) karakterisatie of een uniforme eindige-horizon benadering die exacte feedbackcapaciteit voor deze hele klasse kan vastleggen. De overeenkomst in gedrag op korte termijn (tot horizon $N$ ) garandeert geen overeenkomst in de asymptotische capaciteit.
Gödel-Tarski-Löb Gevolgtrekkingen:
Dit is een uniek en diepgaand aspect van het artikel. Omdat het probleem onbeslisbaar is, volgen er logische beperkingen voor elke recursief axiomatiseerbare theorie $T$ die probeert de waarheid van capaciteitsstellingen te formaliseren:
- Gödel (Onvolledigheid): Geen enkele consistente, effectieve theorie kan alle waarheidswaarden van $C_{fb} \geq q$ bewijzen of weerleggen. Er zullen altijd onbeslisbare stellingen zijn.
- Tarski (Ondefinieerbaarheid): De waarheidspredikaat voor capaciteit kan niet intern worden gedefinieerd binnen de theorie zelf.
- Löb (Reflectie): Er kan geen uniforme theorie bestaan die de correctheid van zijn eigen bewijzen voor capaciteitsdrempels kan garanderen (uniforme reflectieprincipe).

4. Significantie en Implicaties

Fundamentele Grens: Het resultaat vestigt een scherpe grens tussen wat mogelijk is en wat fundamenteel onmogelijk is in de informatietheorie. Het bevestigt dat er geen "universele formule" of "universeel algoritme" bestaat voor exacte feedbackcapaciteit, zelfs niet voor redelijk eenvoudige kanaalmodellen.
Methodologische Richting: Het artikel weerlegt niet de bestaande positieve resultaten voor specifieke subclasses (zoals de werken van Chen-Berger of Yang-Kavcić-Tatikonda). Integendeel, het onderstreept dat succesvolle theorieën afhankelijk zijn van specifieke structurele aannames (zoals contractiviteit of mengingseigenschappen) die de onbeslisbaarheid omzeilen.
Benadering vs. Exactheid: Het resultaat geldt strikt voor exacte oneindige-horizon berekeningen. Het sluit niet uit dat benaderingsalgoritmen, eindige-horizon optimalisatie, of beslissingen met een "promise gap" (waarbij we zeker weten dat de capaciteit ver genoeg van de drempel ligt) wel beslisbaar zijn.
Interdisciplinaire Impact: De koppeling van informatietheorie aan de onvolledigheidsstellingen van Gödel en de ondefinieerbaarheid van Tarski biedt een nieuw perspectief op de grenzen van wiskundige formalisering in de communicatiewetenschap. Het suggereert dat bepaalde vragen over communicatiekanalen fundamenteel buiten het bereik van formele bewijssystemen vallen.

Conclusie:
Dit artikel bewijst dat het zoeken naar een universele, exacte oplossing voor de feedbackcapaciteit van kanaalmodellen met geheugen een onmogelijke opgave is. De complexiteit van deze systemen is zodanig dat ze de grenzen van berekenbaarheid en formele logica overschrijden, wat betekent dat toekomstige vooruitgang moet komen via het identificeren van specifieke, goed-gedragde subclasses en benaderingsmethoden, in plaats van het zoeken naar een universele exacte theorie.