🔢 mathematics

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

Ce papier démontre que le problème de décision exact concernant la capacité de rétroaction des canaux à états finis est indécidable, établissant ainsi une limitation fondamentale qui empêche toute réduction aux systèmes d'équations polynomiales et entraîne des phénomènes d'incomplétude de Gödel-Tarski-Löb pour les théories formelles capables de représenter ce prédicat.

Auteurs originaux : Angshul Majumdar

Publié 2026-03-19

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Angshul Majumdar

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

📡 Le Titre : Quand Shannon rencontre les limites de la logique

Sujet : La capacité de communication des canaux à mémoire avec retour d'information.
Le problème : Peut-on calculer exactement la limite maximale d'information qu'un canal de communication peut transmettre ?

Imaginez que vous essayez de remplir un seau avec de l'eau (l'information) en utilisant un tuyau (le canal de communication). La question est : quelle est la taille exacte du seau ?

1. Le Contexte : Un labyrinthe avec des pièges

Dans le monde des télécommunications, on utilise souvent des modèles appelés canaux à états finis.

L'analogie du labyrinthe : Imaginez un labyrinthe où vous êtes un messager. À chaque étape, vous choisissez un chemin (envoyer un 0 ou un 1). Le labyrinthe a des "pièges" ou des "états" qui changent selon votre choix et ce que vous entendez en retour.
Le retour d'information (Feedback) : C'est comme si, après chaque pas, un gardien vous chuchotait ce qu'il a vu, vous permettant d'ajuster votre prochaine étape.
L'objectif : Trouver la stratégie parfaite pour envoyer le maximum de messages sans erreur, même si le labyrinthe est très complexe.

Jusqu'à présent, pour des labyrinthes simples, les mathématiciens avaient trouvé des formules exactes pour calculer cette capacité. Mais que se passe-t-il si le labyrinthe est un peu plus compliqué, mais toujours logique (avec des nombres rationnels) ?

2. La Révolution : La découverte de l'impossibilité

L'auteur, Angshul Majumdar, a prouvé quelque chose de très surprenant et de fondamental : Il est impossible de créer un algorithme universel qui calcule la capacité exacte de ce type de canal.

L'analogie du "Test de Turing" inversé :
Imaginez que vous avez un robot très intelligent capable de résoudre n'importe quel problème mathématique. Vous lui donnez la description d'un labyrinthe spécifique et vous lui demandez : "Peut-on envoyer plus de 50 % d'information à travers ce labyrinthe ?"

L'auteur a prouvé que ce robot ne pourra jamais répondre avec certitude pour tous les labyrinthes possibles.

Pour certains labyrinthes, il répondra "Oui".
Pour d'autres, "Non".
Mais pour une catégorie précise de labyrinthes (ceux décrits dans l'article), le robot restera bloqué dans une boucle infinie ou donnera une réponse fausse. Il n'existe aucune recette magique (algorithme) qui fonctionne pour tous les cas.

3. Pourquoi est-ce si difficile ? (Le problème de l'horizon infini)

Le papier explique pourquoi c'est impossible en utilisant une idée brillante : le piège du temps.

L'analogie du caméléon :
Imaginez deux caméléons, le "Caméléon A" et le "Caméléon B".
- Pendant les 1000 premières minutes, ils se comportent exactement de la même façon : ils changent de couleur de la même manière, réagissent pareillement. Si vous les observez pendant 1000 minutes, vous penserez qu'ils sont identiques.
- Mais après 1000 minutes, le Caméléon A commence à changer de couleur de façon très efficace (il transmet beaucoup d'information), tandis que le Caméléon B reste bloqué et ne transmet rien.
Le problème est que pour savoir quelle est la capacité exacte (sur une durée infinie), il faut attendre que le caméléon révèle son vrai visage. Mais comme le labyrinthe peut être construit pour retarder ce moment révélateur aussi longtemps qu'on veut (1 million d'années, 1 milliard d'années), aucun calcul fini ne peut prédire le résultat final.

Conclusion : On ne peut pas deviner le résultat final en regardant seulement le début de l'histoire.

4. Les Conséquences : Au-delà des mathématiques

Ce papier ne dit pas juste "c'est dur à calculer". Il dit "c'est fondamentalement impossible". Cela a des conséquences profondes :

Le mur de la logique (Gödel, Tarski, Löb) :
Le papier relie ce problème à la logique pure. Il dit que si vous essayez de créer un système de règles parfait (un livre de lois mathématiques) pour prédire ces capacités, ce système sera toujours incomplet.
- Analogie : C'est comme essayer de écrire un livre qui contient toutes les vérités de l'univers. Gödel a prouvé qu'un tel livre est impossible : il y aura toujours des vérités que le livre ne pourra pas prouver. Ici, la "vérité" est la capacité exacte du canal, et le "livre" est notre système mathématique.
Pas de solution "algébrique" :
Souvent, les problèmes complexes peuvent être réduits à des équations polynomiales (des calculs avec des x et des y). Ce papier dit : "Non, ce problème est trop sauvage pour être enfermé dans de simples équations." Il échappe à toute méthode de calcul standard.

5. Ce que cela ne veut PAS dire

Il est important de ne pas être pessimiste !

Ce n'est pas la fin de la communication : Cela ne signifie pas qu'on ne peut pas communiquer efficacement.
Les approximations fonctionnent : On peut toujours trouver des réponses "presque exactes" ou des solutions pour des labyrinthes très spécifiques et simples.
La vraie leçon : Cela nous dit que nous ne devons pas chercher une "formule universelle" magique pour tous les cas. La recherche doit se concentrer sur des cas particuliers bien définis ou sur des méthodes d'approximation.

En résumé

Ce papier est un panneau "Arrêt" posé sur la route de la recherche en théorie de l'information. Il dit :

"Vous ne pourrez jamais construire un ordinateur ou un algorithme capable de calculer la capacité exacte de n'importe quel canal de communication avec retour d'information, même si ce canal semble simple. C'est une limite fondamentale de la logique et des mathématiques, pas juste un manque de puissance de calcul."

C'est une découverte qui nous force à changer de stratégie : au lieu de chercher la perfection absolue pour tout, il faut apprendre à naviguer dans les zones où la perfection est possible, et accepter l'approximation ailleurs.

1. Problématique et Contexte

L'article s'attaque au problème fondamental de la capacité de rétroaction (feedback capacity) pour les canaux à états finis (Finite-State Channels - FSC). Bien que la capacité de Shannon soit bien définie pour les canaux sans mémoire, l'analyse exacte pour les canaux avec mémoire et rétroaction reste un défi majeur.

Le problème central étudié est un problème de décision exact :
Étant donné un encodage $e$ d'un canal à états finis rationnel, unifilaire, binaire (entrée/sortie), avec une distribution initiale rationnelle spécifiée, et un seuil rationnel $q$ , peut-on décider algorithmiquement si la capacité de rétroaction exacte $C_{fb}(W_e, \pi_{1,e})$ est supérieure ou égale à $q$ ?

Formellement, on cherche à déterminer la vérité du prédicat :
$Cap(e, q) \iff C_{fb}(W_e, \pi_{1,e}) \ge q$

L'auteur insiste sur le caractère exact du problème : il ne s'agit pas d'une approximation, d'une borne additive, ni d'un problème sur un horizon fini, mais bien de la capacité asymptotique exacte sur un horizon infini.

2. Méthodologie et Construction

L'article utilise une approche combinant la théorie de l'information, la théorie de la calculabilité et la logique mathématique.

A. Classe de Canaux Restreinte

Pour prouver l'impossibilité, l'auteur ne se place pas dans un cadre général, mais restreint le problème à une classe très spécifique de canaux :

Entrées et sorties binaires ( $\{0, 1\}$ ).
Paramètres rationnels (probabilités de transition et distribution initiale).
Propriété unifilaire : L'état suivant $S_{t+1}$ est déterminé de manière déterministe par l'état actuel, l'entrée et la sortie ( $S_{t+1} = f(S_t, X_t, Y_t)$ ).
Construction à activation retardée : L'auteur construit une famille de canaux où l'état du canal progresse de manière déterministe pendant $N$ étapes (phase de « délai ») avant d'atteindre un état absorbant actif.

B. Le Mécanisme de Réduction

La preuve repose sur une réduction many-one à partir d'un problème indécidable connu (comme le problème de l'arrêt ou un problème arithmétique équivalent).

Construction de deux canaux : Pour chaque instance d'un problème indécidable, on construit deux canaux, $Ch(N)_{good}$ $C h (N)_{g oo d}$ et $Ch(N)_{bad}$ $C h (N)_{ba d}$ , partageant la même structure de délai.
- Phase de délai ( $t \le N+1$ ) : Les deux canaux produisent une sortie déterministe (0) quel que soit l'entrée. L'information dirigée est nulle.
- Phase active ( $t > N+1$ ) :
  - Le canal « bon » ($good$) devient un canal sans bruit (capacité 1).
  - Le canal « mauvais » ($bad$) devient un canal purement aléatoire (capacité 0).
Comportement à horizon fini : Pour tout horizon $n \le N+1$ , les deux canaux sont indiscernables et ont une capacité nulle.
Comportement asymptotique : La capacité exacte diffère radicalement (1 pour le bon, 0 pour le mauvais).

3. Contributions Clés et Résultats

L'article établit quatre résultats majeurs :

1. Indécidabilité du Seuil Exact (Théorème IV.4)

Il n'existe aucun algorithme capable de décider si $C_{fb}(W_e, \pi_{1,e}) \ge q$ pour la classe des canaux unifilaires rationnels.

Conséquence : Le langage $L_{Cap} = \{ \langle e, q \rangle \mid C_{fb} \ge q \}$ est indécidable.
Implication structurelle : Il n'existe pas de caractérisation uniforme par horizon fini. Même si l'on connaît les valeurs optimisées pour un nombre fini d'horizons $V_n$ , cela ne suffit pas à déterminer la capacité asymptotique exacte, car le comportement asymptotique peut être arbitrairement retardé.

2. Barrière Algébrique Réelle ( $\exists\mathbb{R}$ )

L'auteur démontre que le problème de décision exacte n'appartient pas à la classe de complexité $\exists\mathbb{R}$ (Théorie Existentielle des Réels).

La théorie existentielle des réels (ETR) est décidable (dans PSPACE) et concerne les systèmes d'équations et d'inégalités polynomiales.
Puisque $L_{Cap}$ est indécidable, il ne peut pas être réduit à un problème ETR. Cela signifie qu'il n'existe pas de formulation universelle de la capacité de rétroaction sous forme de système d'équations polynomiales finies sur les réels.

3. Conséquences de Calculabilité pour la Certification

Il est impossible d'élaborer un schéma universel de « certification exacte » ou une caractérisation par un nombre fini d'états auxiliaires qui serait valide pour toute la classe des canaux considérée. Toute tentative de bornage exact universel échouera.

4. Implications Logiques (Gödel-Tarski-Löb)

C'est la contribution la plus originale (« Shannon meets Gödel »). En formalisant la vérité du seuil de capacité dans une théorie axiomatique récursive $T$ (étendant l'arithmétique de base) :

Incomplétude (Gödel) : Aucune théorie axiomatique récursive et cohérente ne peut décider tous les cas de vérité pour le prédicat de capacité. Il existe des énoncés de capacité qui sont vrais mais non démontrables dans $T$ .
Indéfinissabilité (Tarski) : Il n'existe pas de prédicat de vérité interne dans $T$ capable de définir correctement la vérité sémantique des énoncés de capacité.
Obstruction de Löb : Aucune théorie cohérente ne peut prouver le principe de réflexion uniforme pour ses propres preuves de seuils de capacité (c'est-à-dire, elle ne peut pas prouver que « si je prouve que la capacité est $\ge q$ , alors elle est effectivement $\ge q$ ») pour tous les cas.

4. Signification et Portée

Limites Fondamentales : Ce résultat établit une frontière rigoureuse entre les théories exactes réussies pour des sous-classes structurées (comme les canaux à mémoire spécifique) et l'impossibilité d'une théorie exacte universelle pour les canaux à états finis généraux.
Pas de Pessimisme sur l'Approximation : L'article précise qu'il ne remet pas en cause les méthodes d'approximation, les bornes calculables, ou les résultats pour des sous-classes spécifiques. Il se concentre uniquement sur la décision exacte et asymptotique.
Changement de Paradigme : La recherche future ne doit pas chercher un algorithme universel exact, mais plutôt identifier les sous-classes structurelles (contraction, mélange, régularité) où la décidabilité est restaurée, ou se concentrer sur des schémas d'approximation certifiés.

En résumé, l'article démontre que la capacité de rétroaction exacte pour les canaux à états finis échappe à toute procédure algorithmique universelle, à toute formulation algébrique finie, et à toute axiomatisation complète, révélant ainsi une limite fondamentale de la théorie de l'information computationnelle.