💬 NLP

ZX-Calculus:Trace-Indexed Dependent Types and Epistemic Semantics

Cet article introduit le ZX-Calculus, une extension conservatrice de la théorie des types dépendants de Martin-Löf qui intègre des types indexés par la trace, une sémantique de préschémas non monotone et la révision de croyances AGM constructive, fournissant un cadre vérifié par Coq qui établit des théorèmes clés tout en révélant une tension fondamentale entre la révision de croyances dépendante du chemin et la cohérence des foncteurs.

Auteurs originaux : Peng Chen

Publié 2026-06-03

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Peng Chen

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

Imaginez que vous essayez de construire un programme informatique qui ne se contente pas de connaître des faits, mais qui se souvient aussi de comment il les a appris, peut changer d'avis lorsqu'il reçoit de nouvelles informations, et peut prouver que ses changements sont cohérents.

Ce document, intitulé « ZX-Calculus », propose un nouveau langage mathématique (une extension d'un système appelé MLTT) pour faire précisément cela. L'auteur, Peng Chen, traite la connaissance non pas comme une liste statique de faits, mais comme un film qui se déroule au fil du temps.

Voici la décomposition des idées du document en utilisant des analogies simples :

1. La bobine de film (Types de traces / Trace Types)

Le Problème : Dans la plupart des systèmes informatiques, si vous demandez « Quel est l'état actuel ? », le système donne la réponse mais oublie l'historique. C'est comme regarder une photo unique d'un accident de voiture ; vous voyez les dégâts, mais vous ne savez pas si le conducteur roulait trop vite ou si les freins ont lâché.
La Solution : Le document introduit les « Types de traces » (Trace Types). Considérez cela comme une bobine de film plutôt qu'une photo.

Chaque fois que le système apprend quelque chose ou change, une nouvelle « image » est ajoutée à la bobine.
Le système ne stocke pas seulement l'état final ; il stocke toute la séquence d'événements (la « trace ») qui y a conduit.
L'Innovation : Le document compare cela à une méthode existante appelée « Star(Step) ». L'auteur soutient que bien que les deux méthodes puissent décrire le même chemin, leurs « télécommandes » (interfaces) sont différentes. La nouvelle méthode (FinTrace) possède un bouton qui vous permet d'appuyer directement sur « Événement ». Cela rend beaucoup plus facile de poser des questions telles que : « Que s'est-il passé spécifiquement lorsque l'événement 'Alarme Incendie' s'est produit ? » sans avoir à fouiller à travers des couches de code pour le trouver.

2. La gomme et le carnet (Sémantique de faisceaux & Non-monotonie)

Le Problème : Dans la logique traditionnelle, une fois que vous avez prouvé quelque chose, cela reste vrai pour toujours. Mais dans le monde réel, la connaissance est non-monotone. Si je crois que « Il pleut » parce que je vois un nuage, puis que je sors et que je vois le soleil, ma croyance change. Mon ancienne croyance n'est pas seulement « fausse » ; elle est rétractée.
La Solution : Le document utilise un concept appelé « Sémantique de faisceaux » (Sheaf Semantics). Imaginez un carnet où vous notez ce que vous savez.

Au fil du temps (la « trace » s'allonge), vous devrez peut-être effacer une phrase que vous avez écrite plus tôt parce qu'une nouvelle preuve la contredit.
En mathématiques, habituellement, on ne peut pas « effacer » une preuve sans briser le système. Ce document crée un type spécial de carnet où « l'effacement » est une caractéristique structurelle, et non un bug.
L'Idée Clé : Le document prouve que les règules du carnet (la logique) restent parfaites et stables, même si le contenu (les croyances) peut changer ou disparaître. Il sépare les « règles d'écriture » du « contenu de l'histoire ».

3. Le débatteur rationnel (Révision de croyance AGM)

Le Problème : Lorsqu'un agent intelligent (comme un robot ou une personne) reçoit une nouvelle information qui contredit ce qu'il croit, comment doit-il changer d'avis ? Il ne devrait pas simplement tout supprimer et repartir de zéro ; il devrait conserver autant de ses anciennes connaissances que possible tout en acceptant la nouvelle vérité. C'est ce qu'on appelle le cadre AGM (nommé d'après trois logiciens).
La Solution : Le document construit un algorithme constructif (une recette étape par étape) pour ce processus.

L'échelle d'« Enracinement » : Imaginez que chaque croyance que vous avez se trouve sur un barreau d'une échelle. Certaines croyances sont très profondes (comme « 2+2=4 » ou « Le soleil se lève à l'est »). D'autres sont superficielles (comme « Il pleut aujourd'hui »).
L'Algorithme : Lorsqu'une nouvelle information arrive (ex: « Le soleil se couche à l'est »), le système examine l'échelle. Il commence par retirer les croyances les plus superficielles en premier jusqu'à ce que le conflit soit résolu. Il ne touche aux croyances profondes que si c'est absolument nécessaire.
La Preuve : Le document fournit une preuve mathématique rigoureuse que cet algorithme fonctionne parfaitement et suit toutes les règles du changement de croyance rationnel. Il prouve même que cela fonctionne même lorsque vous devez gérer des combinaisons complexes de « ET » et de « OU » de nouvelles informations.

4. Le bug dans le système (Échec de la BP-comp)

Le Problème : Les auteurs ont tenté de voir si tout ce système pouvait être décrit comme un flux unique, lisse et continu (un « faisceau » ou « sheaf »). Ils voulaient savoir : « Si je mets à jour mes croyances étape par étape (de A à B, puis de B à C), est-ce la même chose que de mettre à jour directement de A à C ? »
Le Résultat : Non. Le document prouve que pour ce type spécifique de révision de croyance, l'ordre compte.

L'Analogie : Imaginez que vous naviguez dans un labyrinthe. Si vous tournez à gauche puis à droite, vous finissez à un endroit différent de si vous tournez à droite puis à gauche.
Le document montre que « mettre à jour ses croyances » est comme naviguer dans un labyrinthe. Vous ne pouvez pas simplement sauter des étapes. La « Mise à jour directe » est souvent différente de la « Mise à jour étape par étape ».
La Correction : Au lieu de forcer le système à être un flux fluide, les auteurs définissent une structure nouvelle, légèrement plus lâche, appelée SSRS (Système de Révision à Étape Unique). Cette structure admet que « l'histoire compte » et que vous devez traiter les mises à jour une étape à la fois. Ils prouvent que leur système de croyance s'intègre parfaitement dans cette nouvelle structure.

5. La Vérification (Mécanisation Coq)

L'auteur n'a pas seulement écrit ces idées ; il a construit un vérificateur de preuves numérique (en utilisant un outil appelé Coq).

Il a écrit 34 preuves mathématiques complètes qui vérifient ses affirmations.
Il a prouvé que le système « Étape par Étape » (SSRS) fonctionne et que la « Mise à jour Directe » échoue, exactement comme ils l'avaient prédit.
C'est comme si un robot avocat vérifiait chaque étape d'un argument juridique pour s'assurer qu'il n'y a aucune faille.

Résumé

Ce document construit un moteur mathématique pour la connaissance dynamique.

Il traite l'histoire comme un citoyen de premier rang (on ne peut pas simplement regarder le présent ; il faut regarder le chemin parcouru).
Il permet aux croyances d'être rétractées sans briser le système logique.
Il fournit une recette rationnelle pour changer d'avis lorsque l'on reçoit de nouvelles informations.
Il prouve que l'histoire compte : on ne peut pas toujours sauter des étapes lors de la mise à jour de ses connaissances.

L'objectif ultime est de créer une base pour des systèmes capables d'apprendre, de s'adapter et de raisonner sur leurs propres changements d'une manière mathématiquement garantie d'être cohérente.

Résumé Technique : ZX-Calculus

Énoncé du Problème

La logique épistémique classique et la sémantique opérationnelle standard font face à trois limitations fondamentales lors de la modélisation de systèmes dynamiques à l'évolution de la connaissance :

Les traces comme méta-objets : Les traces d'exécution sont typiquement traitées comme des objets de méta-niveau plutôt que comme des données de premier rang au sein du système de types. Bien que la Théorie des Types Homotopiques (HoTT) offre des chemins inversibles et que les types de session caractérisent les protocoles, ils manquent d'un mécanisme natif pour représenter des histoires causales dirigées et non inversibles où la séquence spécifique d'événements est une constituante primaire du type.
Monotonie vs Non-Monotonie : Les théories de types standards sont monotones ; l'ajout d'informations n'invalide jamais les preuves précédentes. Cependant, la connaissance épistémique est intrinsèquement non monotone (rétractable). L'ajout direct de règles de preuve non monotones à une théorie de types détruit la normalisation et la cohérence.
Révision AGM Constructive : Les approches constructives existantes de la révision des croyances (par exemple, dans la Logique Épistémique Dynamique ou le raisonnement non monotone) manquent souvent d'algorithmes exécutables pour la contraction par rencontre partielle, échouent à emballer les résultats de contraction avec des témoins de correction sous forme de types dépendants, ou opèrent dans des cadres statiques sans sémantique indexée par les traces.

Méthodologie

Le papier propose ZX-Calculus, une extension conservatrice de la Théorie des Types Dépendants de Martin-Löf (MLTT). Il ne modifie pas les règles structurelles de base de MLTT mais introduit de nouvelles structures de types et interprétations sémantiques pour intégrer trois couches :

Types indexés par les traces : Une famille inductive FinTrace représentant des traces d'exécution finies comme des objets constructifs.
Sémantique de Faisceaux (Sheaf Semantics) : Interprétation des propositions indexées par les traces comme des faisceaux contravariants sur une catégorie de traces libre, permettant une non-monotonie sémantique via des applications de restriction non surjectives tout en préservant la monotonie prouvabilité de la théorie.
Révision AGM Constructive : Une implémentation typée de la révision des croyances du cadre AGM (Alchourrón–Gärdenfors–Makinson), utilisant des types $\Sigma$ pour emballer les ensembles de croyances avec des preuves constructives d'adhérence aux postulats AGM.

Le cadre est vérifié à l'aide d'une mécanisation Coq comprenant 34 preuves complètes, avec un accent particulier sur l'échec de la composition de faisceaux dans la révision séquentielle et la cohérence des systèmes de révision à étape unique.

Contributions Clés

1. Types de Traces et Conception d'Interface

Le papier introduit FinTrace, une famille inductive de traces finies entre des états.

Comparaison avec Star(Step) : Les auteurs prouvent que FinTrace est isomorphe à la clôture de Kleene Star(Step) en tant que collections de chemins (Proposition 3.2). Cependant, ils ne sont pas judiciairement égaux.
Avantage de l'Interface : L'éliminateur structurel TraceElim prend l'étiquette d'événement e : Event comme un paramètre explicite dans sa fonction d'étape. Cela contraste avec StarElim, qui nécessite de déballer un type $\Sigma$ pour récupérer l'information de l'événement. Ce choix de conception élève la structure causale de l'événement en tant que composante native de l'induction de trace, facilitant la sémantique de faisceau pilotée par les événements et le rejeu déterministe.
Méta-Théorie : Le papier établit un cadre de Canonicité via des relations logiques et des candidats de réductibilité. Une contribution technique critique est le Lemme de Transport (Lemme 3.12), qui garantit que la réductibilité est transportée de manière stable sous l'extension de trace. La pleine mécanisation de l'étape RC-elim pour les motifs d'ordre supérieur est notée comme un travail futur.

2. Sémantique de Faisceaux et Non-Monotonie

Le papier interprète la connaissance comme un pré-faisceau sur la catégorie de traces $\mathbf{bTf}$ .

Théorème de Séparation : Le Théorème 4.5 démontre une séparation claire entre la monotonie prouvable (qui est préservée) et la non-monotonie sémantique. L'invalidation de la connaissance est modélisée par la non-surjectivité des applications de restriction, et non comme une contradiction logique.
CwF Initial : Le modèle de terme est prouvé comme étant le CwF (Category with Families) initial (Théorème 4.8), établissant une propriété universelle syntaxique où la syntaxe détermine uniquement l'interprétation sémantique.

3. Révision des Croyances AGM Constructive

Le papier fournit le premier algorithme explicite de contraction par rencontre partielle dans MLTT (Algorithme 6.3).

Algorithme 6.3 : Cet algorithme supprime itérativement les croyances les moins ancrées pour satisfaire les conditions de contraction (C1–C4). Il est entièrement vérifié pour habiter le type $\Sigma$ Selτ(ψ), qui emballe l'ensemble de croyances résultant avec des preuves de sa correction.
Lemme d'Ancrage Disjonctif : Le Lemme 6.7 fournit une preuve constructive entièrement autonome que l'ancrage d'une disjonction est équivalent à l'ancrage maximal de ses disjonctes. Ce lemme est essentiel pour prouver les postulats complexes de l'AGM R7 et R8.
Postulats AGM Complets : Le papier prouve que le système de révision indexé par les traces satisfait les huit postulats classiques de l'AGM (Théorèmes 6.9–6.12), intégrant la théorie AGM classique dans un cadre dynamique piloté par les événements.

4. Intégration et Cohérence

Une tension centrale est identifiée : le "principe de changement minimal" de la révision AGM est sensible au chemin, tandis que la sémantique de faisceaux exige une composition invariante par rapport au chemin (BP-comp).

Échec de BP-comp : Le Théorème 7.1 prouve que le foncteur de révision des croyances $B_{AGM}$ n'est pas un faisceau ; la loi de composition échoue pour la révision AGM séquentielle. Un contre-modèle vérifié par Coq est fourni.
Systèmes de Révision à Étape Unique (SSRS) : Pour résoudre cela, le papier introduit le SSRS (Définition 7.2), une structure plus faible qui abandonne les contraintes de composition globale mais conserve des mises à jour à étape unique bien définies. Le Théorème 7.4 prouve que $B_{AGM}$ est un SSRS valide, établissant une intégration cohérente des traces, des faisceaux et de la révision des croyances au sein de ce cadre intermédiaire.

Résultats et Vérification

Mécanisation Coq : Le papier inclut une formalisation Coq avec 34 preuves complètes et zéro admit pour les résultats d'intégration de base : le Théorème d'Échec de BP-comp et la Cohérence du SSRS.
Statut des Preuves :
- Complète : Proposition 3.2, Lemmes 3.12/3.13, correction de l'Algorithme 6.3, postulats AGM R1–R8, Lemme d'Ancrage Disjonctif, Échec de BP-comp, et Cohérence du SSRS.
- En attente de mécanisation : L'étape RC-elim du Théorème de Canonicité (Théorème 3.14) est actuellement supportée par un argument vérifié à la main ; la pleine mécanisation est listée comme un travail futur.

Signification et Revendications

Le papier revendique de fournir une extension conservatrice de MLTT qui unifie les traces historiques, l'évolution non monotone de la connaissance et la révision constructive des croyances sans perturber la stabilité méta-théorique de la théorie des types sous-jacente.

Unification : Il démontre que "comment le système est parvenu à son état actuel" peut être une constituante native du système de types, permettant un raisonnement constructif sur les propriétés dépendantes de l'histoire.
Logique Épistémique Dynamique : En intégeant la révision AGM dans un cadre indexé par les traces, le système généralise la théorie AGM classique pour décrire l'évolution de la connaissance d'agents cognitifs réels, où différentes séquences d'événements induisent différentes structures d'ancrage épistémique.
Rigueur Fondamentale : Le travail clarifie la tension structurelle entre la fonctorialité de faisceau et la révision des croyances, proposant le SSRS comme le modèle catégorique correct pour les systèmes de croyances dynamiques.
Vérification Constructive : Contrairement à l'AGM classique qui repose sur des définitions existentielles, ce cadre fournit des algorithmes exécutables et des témoins constructifs pour la contraction des croyances, rendant le processus de révision informatiquement vérifiable.

Le papier conclut que le ZX-Calculus offre une fondation vérifiable pour la connaissance dynamique, les mécanismes de rétractation et la surveillance au moment de l'exécution, avec des travaux futurs orientés vers la complétude sémantique totale, les extensions de traces infinies et l'achèvement des obligations Coq restantes.