Resumen Técnico: ZX-Calculus

Planteamiento del Problema

La lógica epistémica clásica y la semántica operacional estándar enfrentan tres limitaciones fundamentales al modelar sistemas dinámicos de evolución del conocimiento:

1. Trazas como Meta-Objetos: Las trazas de ejecución se tratan típicamente como objetos de meta-nivel en lugar de datos de primer orden dentro del sistema de tipos. Aunque la Teoría de Tipos Homotópicos (HoTT) ofrece caminos invertibles y los tipos de sesión caracterizan protocolos, carecen de un mecanismo nativo para representar historias causales dirigidas y no invertibles donde la secuencia específica de eventos es un constituyente primario del tipo.
2. Monotonicidad vs. No-Monotonicidad: Las teorías de tipos estándar son monotónicas; añadir información nunca invalida pruebas previas. Sin embargo, el conocimiento epistémico es inherentemente no-monótono (retractil). Añadir directamente reglas de prueba no-monótonas a una teoría de tipos destruye la normalización y la consistencia.
3. Revisión AGM Constructiva: Los enfoques constructivos existentes para la revisión de creencias (por ejemplo, en la Lógica Epistémica Dinámica o el razonamiento no-monótono) a menudo carecen de algoritmos ejecutables para la contracción de encuentro parcial, fallan al empaquetar los resultados de la contracción con testigos de corrección como tipos dependientes, o operan en marcos estáticos sin semántica indexada por trazas.

Metodología

El artículo propone ZX-Calculus, una extensión conservadora de la Teoría de Tipos Dependientes de Martin-Löf (MLTT). No altera las reglas estructurales centrales de MLTT, sino que introduce nuevas estructuras de tipos e interpretaciones semánticas para integrar tres capas:

1. Tipos Indexados por Trazas: Una familia inductiva FinTrace que representa trazas de ejecución finitas como objetos constructivos.
2. Semántica de Haces (Sheaf Semantics): Interpretación de proposiciones indexadas por trazas como haces contravariantes sobre una categoría de trazas libre, permitiendo la no-monotonicidad semántica mediante mapas de restricción no suryectivos mientras se preserva la monotonicidad proof-teórica.
3. Revisión AGM Constructiva: Una implementación tipológica de la estructura de revisión de creencias AGM (Alchourrón–Gärdenfors–Makinson), utilizando tipos-$\Sigma$ para empaquetar conjuntos de creencias con pruebas constructivas de adherencia a los postulados AGM.

El marco se verifica mediante una mecanización en Coq que comprende 34 pruebas completas, con un enfoque específico en el fallo de la composición de haces en la revisión secuencial y la coherencia de los sistemas de revisión de paso único.

Contribuciones Clave

1. Tipos de Trazas y Diseño de Interfaz

El artículo introduce FinTrace, una familia inductiva de trazas finitas entre estados.

• Comparación con Star(Step): Los autores demuestran que FinTrace es isomórfica a la clausura de Kleene Star(Step) como colecciones de caminos (Proposición 3.2). Sin embargo, no son de igualdad judgemental.
• Ventaja de la Interfaz: El eliminador estructural TraceElim toma la etiqueta de evento e : Event como un parámetro explícito en su función de paso. Esto contrasta con StarElim, que requiere desempaquetar un tipo-$\Sigma$ para recuperar la información del evento. Esta elección de diseño eleva la estructura causal del evento a un componente nativo de la inducción de trazas, facilitando la semántica de haces dirigida por eventos y la reproducción determinista.
• Meta-Teoría: El artículo establece un marco de Canonicidad mediante relaciones lógicas y candidatos de reducibilidad. Una contribución técnica crítica es el Lema de Transporte (Lema 3.12), que asegura que la reducibilidad se transporta de forma estable bajo la extensión de la traza. Se señala como trabajo futuro la mecanización completa del paso RC-elim para motivos de orden superior.

2. Semántica de Haces y No-Monotonicidad

El artículo interpreta el conocimiento como un pre-haz sobre la categoría de trazas $\mathbf{bTf}$.

• Teorema de Separación: El Teorema 4.5 demuestra una clara separación entre la monotonicidad proof-teórica (que se preserva) y la no-monotonicidad semántica. La invalidación del conocimiento se modela como la no-suryectividad de los mapas de restricción, no como una contradicción lógica.
• CwF Inicial: Se demuestra que el modelo de términos es el CwF (Categoría con Familias) inicial (Teorema 4.8), estableciendo una propiedad universal sintáctica donde la sintaxis determina únicamente la interpretación semántica.

3. Revisión de Creencias AGM Constructiva

El artículo proporciona el primer algoritmo constructivo explícito para la contracción de encuentro parcial en MLTT (Algoritmo 6.3).

• Algoritmo 6.3: Este algoritmo elimina iterativamente las creencias menos arraigadas para satisfacer las condiciones de contracción (C1–C4). Está totalmente verificado para habitar el tipo-$\Sigma$ Selτ(ψ), que empaqueta el conjunto de creencias resultante con pruebas de su corrección.
• Lema de Arraigo Disyuntivo: El Lema 6.7 proporciona una prueba constructiva totalmente autónoma de que el arraigo de una disyunción es equivalente al arraigo máximo de sus disyuntos. Este lema es esencial para probar los complejos postulados AGM R7 y R8.
• Postulados AGM Completos: El artículo demuestra que el sistema de revisión indexado por trazas satisface los ocho postulados clásicos de AGM (Teoremas 6.9–6.12), integrando la teoría AGM clásica en un marco dinámico dirigido por eventos.

4. Integración y Coherencia

Se identifica una tensión central: el "principio de cambio mínimo" de la revisión AGM es sensible a la trayectoria, mientras que la semántica de haces requiere composición invariante de trayectoria (BP-comp).

• Fallo de BP-comp: El Teorema 7.1 demuestra que el funtor de revisión de creencias $B_{AGM}$ no es un haz; la ley de composición falla para la revisión AGM secuencial. Se proporciona un contra-modelo verificado en Coq.
• Sistemas de Revisión de Paso Único (SSRS): Para resolver esto, el artículo introduce SSRS (Definición 7.2), una estructura más débil que descarta las restricciones de composición global pero retiene actualizaciones de paso único bien definidas. El Teorema 7.4 demuestra que $B_{AGM}$ es un SSRS válido, estableciendo una integración coherente de trazas, haces y revisión de creencias dentro de este marco intermedio.

Resultados y Verificación

• Mecanización en Coq: El artículo incluye una formalización en Coq con 34 pruebas completas y cero admits para los resultados de integración central: el Teorema del Fallo de BP-comp y la Coherencia de SSRS.
• Estado de la Prueba:
  • Completa: Proposición 3.2, Lemas 3.12/3.13, corrección del Algoritmo 6.3, postulados AGM R1–R8, Lema de Arraigo Disyuntivo, Fallo de BP-comp y Coherencia de SSRS.
  • Pendiente de Mecanización: El paso RC-elim del Teorema de Canonicidad (Teorema 3.14) está actualmente respaldado por un argumento verificado a mano; la mecanización completa se lista como trabajo futuro.

Significancia y Reivindicaciones

El artículo afirma proporcionar una extensión conservadora de MLTT que unifica las trazas históricas, la evolución no-monótona del conocimiento y la revisión de creencias constructiva sin romper la estabilidad meta-teórica de la teoría de tipos subyacente.

• Unificación: Demuestra que "cómo el sistema llegó a su estado actual" puede ser un componente nativo del sistema de tipos, permitiendo el razonamiento constructivo sobre propiedades dependientes de la historia.
• Lógica Epistémica Dinámica: Al embeber la revisión AGM en un marco indexado por trazas, el sistema generaliza la teoría AGM clásica para describir la evolución del conocimiento de agentes cognitivos reales, donde diferentes secuencias de eventos inducen diferentes estructuras de arraigo epistémico.
• Rigor Fundacional: El trabajo clarifica la tensión estructural entre la functorialidad de los haces y la revisión de creencias, proponiendo SSRS como el modelo categórico correcto para sistemas de creencias dinámicos.
• Verificación Constructiva: A diferencia de la AGM clásica que depende de definiciones existenciales, este marco proporciona algoritmos ejecutables y testigos constructivos para la contracción de creencias, haciendo que el proceso de revisión sea computacionalmente verificable.

El artículo concluye que ZX-Calculus ofrece una base verificable para el conocimiento dinámico, mecanismos de retracción y monitoreo en tiempo de ejecución, con trabajos futuros dirigidos hacia la completitud semántica total, extensiones de trazas infinitas y la finalización de las obligaciones restantes de Coq.