💻 computer science

A Logical 3-valued Semantics for Nondeterministic Choice

Este artículo propone una nueva disyunción no determinista simétrica de tres valores dentro del marco de las matrices no deterministas para proporcionar una formalización lógica de los errores computacionales en sistemas reactivos que elimina las asimetrías de evaluación secuencial mientras preserva la conmutatividad y la simetría operacional.

Autores originales: Alessandro Aldini (Dipartimento di Scienze Pure e Applicate Universita' di Urbino, Urbino, Italy), Pierluigi Graziani (Dipartimento di Scienze Pure e Applicate Universita' di Urbino, Urbino, Italy), C

Publicado 2026-07-23

📖 7 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Alessandro Aldini (Dipartimento di Scienze Pure e Applicate Universita' di Urbino, Urbino, Italy), Pierluigi Graziani (Dipartimento di Scienze Pure e Applicate Universita' di Urbino, Urbino, Italy), Claudio Antares Mezzina (Dipartimento di Scienze Pure e Applicate Universita' di Urbino, Urbino, Italy), Gandolfo Vergottini (Dipartimento di Scienze Pure e Applicate Universita' di Urbino, Urbino, Italy)

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que estás de pie en una sala de control concurrida, observando una pantalla gigante que monitorea una flota de drones de entrega. En el mundo de la informática, esta pantalla representa un "sistema lógico": un conjunto de reglas que ayuda a las máquinas a decidir qué es verdadero, qué es falso y qué sucede cuando las cosas salen mal. Usualmente, las computadoras son muy blancas o negras: una luz está encendida (Verdadero) o apagada (Falso). Pero la vida real es caótica. A veces un sensor se rompe, una señal se pierde o un dron simplemente no sabe dónde está. Para manejar esto, los científicos inventaron la "lógica de tres valores", que añade una tercera opción: "Tal vez" o "Desconocido".

Sin embargo, existe un problema complicado cuando estos estados de "Tal vez" se encuentran con la "Elección". Imagina que dos drones intentan elegir una ruta. Si el mapa de un dron está roto (un error), ¿falla toda la misión? ¿O el otro dron simplemente continúa su camino? Las reglas antiguas para las computadoras eran como un policía de tránsito estricto: si un carril tenía un bache, toda la carretera se cerraba. Otras reglas eran como un conductor perezoso que solo mira el carril izquierdo primero; si ese carril está bloqueado, se detiene inmediatamente sin revisar el derecho. Pero en un mundo de drones voladores y computadoras paralelas, las cosas suceden al mismo tiempo. Necesitamos una regla que diga: "Si un camino está roto, tal vez el otro funcione, y no sabremos cuál elegiremos hasta que lo intentemos". Este es el rompecabezas de la "elección no determinista" ante la presencia de errores.

Este artículo, escrito por Alessandro Aldini y su equipo, aborda exactamente ese rompecabezas. Ellos argumentan que las viejas formas de manejar los errores en la lógica computacional son demasiado rígidas o demasiado unilaterales. Proponen una forma completamente nueva de pensar en las elecciones "O" (OR) cuando hay errores involucrados. En lugar de forzar una única respuesta, introducen una regla "simétrica" donde la computadora puede genuinamente lanzar una moneda entre el éxito y el fallo. Prueban que esto funciona utilizando un tipo especial de matemáticas llamadas "matrices no deterministas" y muestran cómo esto puede traducirse en un conjunto estricto de reglas para verificar programas informáticos.

El Problema: Lo "Perezoso" y lo "Infeccioso"

Para entender la solución de los autores, observemos las tres formas antiguas en que las computadoras manejaban una señal rota (llamémosla "Error").

La forma "Perezosa" (McCarthy): Imagina que estás leyendo un menú. Si el primer artículo es "Veneno", dejas de leer inmediatamente y ni siquiera miras el segundo artículo. Así es como funcionan muchos lenguajes de programación. Si la primera parte de una decisión falla, todo se detiene. ¿El problema? Es injusto. Trata el lado izquierdo de una elección como más importante que el derecho. En un mundo donde dos computadoras trabajan juntas de igual manera, este sesgo de "primero la izquierda" no tiene sentido.
La forma "Infecciosa" (Bochvar): Imagina un juego de "Teléfono descompuesto" donde, si una persona susurra una palabra incorrecta, todo el mensaje se vuelve ininteligible. Si cualquier parte de un cálculo tiene un error, el resultado completo se declara como un error. Esto es muy seguro, pero es demasiado pesimista. Si un dron se estrella, ¿por qué debería también quedar en tierra el otro dron que está volando perfectamente?
La forma "Incierta" (Kleene): Este es el punto medio. Si una parte está rota, el resultado es simplemente "desconocido". No hace que todo el sistema colapse, pero tampoco garantiza el éxito.

Los autores señalan que, si bien estas reglas son buenas para tareas simples y paso a paso, fallan cuando tenemos sistemas concurrentes —sistemas donde muchas cosas sucedan al mismo tiempo, como un enjambre de drones o una red de servidores. En estos sistemas, si una rama de una decisión falla, la otra rama aún podría funcionar. Las viejas reglas o bien matan todo el sistema o fuerzan un orden específico de verificación que no existe en la realidad.

La Solución: Un Lanzamiento de Moneda Justo

El equipo introduce una nueva herramienta lógica, un tipo especial de "O" (que ellos llaman $\tilde{\lor}$ ). Piensa en esto como un lanzador de monedas mágico para computadoras.

En su nuevo sistema, si tienes una elección entre "Éxito" y "Error", la computadora no elige simplemente uno u otro. En su lugar, reconoce que ambos resultados son posibles.

Si preguntas: "¿Podemos ir a la Izquierda (Éxito) O a la Derecha (Error)?", la respuesta no es solo "Sí" o "No".
La respuesta es: "Podría ser Sí, o podría ser Error. Aún no lo sabemos, y ambas son posibilidades válidas".

Esto se llama no determinismo simétrico. Trata ambos lados de la elección por igual. No le importa cuál revises primero (a diferencia de la forma "Perezosa"), y no deja que un error arruine toda la fiesta (a diferencia de la forma "Infecciosa"). Simplemente dice: "Si un camino está roto, el sistema podría tener éxito, o podría fallar, y ese es un estado real y válido del mundo".

Cómo lo Probaron

Los autores no solo supusieron que esto funcionaría; construyeron un marco matemático riguroso para probarlo.

La Tabla Mágica (Matrices No Deterministas): Crearon una tabla especial (una "matriz") que enumera todos los resultados posibles. En esta tabla, la celda para "Éxito O Error" no tiene solo una respuesta; tiene un conjunto de respuestas: {Éxito, Error}. Esto permite que la lógica mantenga múltiples posibilidades a la vez.
El Libro de Reglas (Cálculo de Secuentes): Escribieron un nuevo conjunto de reglas (un "cálculo") que las computadoras pueden usar para verificar si un programa es seguro. Demostraron que estas reglas son sound (consistentes/correctas: nunca dan una respuesta errónea) y completas (pueden encontrar la respuesta a cualquier pregunta válida).
Dos Versiones: Mostraron que esto funciona de dos maneras:
- Dinámica: Cada vez que la computadora toma una decisión, lanza la moneda de nuevo. Esto es excelente para sistemas donde las cosas cambian constantemente.
- Estática: La computadora elige una regla una vez y se mantiene con ella. Esto es mejor para sistemas que necesitan ser predecibles.

El "Análisis Profundo": Cinco Valores en lugar de Tres

Para hacer su idea aún más clara, los autores fueron un paso más allá. Se dieron cuenta de que el "Error" en su sistema de tres valores era un poco misterioso. ¿Es un pequeño fallo? ¿Un gran colapso? ¿Un error de dirección?

Así que construyeron un sistema de cinco valores. Tomaron esa única caja de "Error" y la dividieron en tres tipos distintos:

Error Suave (Kleene): Un pequeño contratiempo del que el sistema puede recuperarse.
Error Sensible al Orden (McCarthy): Un error que solo ocurre si revisas las cosas en el orden incorrecto.
Error Fatal (Bochvar): Un colapso total que detiene todo.

Demostraron que su nueva lógica de tres valores "simétrica" es en realidad una versión simplificada de este mundo de cinco valores más detallado. Es como mirar una foto borrosa (tres valores) frente a una foto de alta definición (cinco valores). La foto borrosa es útil cuando no tienes los detalles, pero la foto de alta definición explica por qué ocurre el desenfoque.

Por Qué Esto Importa

Este trabajo es un puente entre cómo pensamos sobre la lógica y cómo se comportan las computadoras en el mundo real. Al crear una lógica que respeta la simetría y permite la incertidumbre genuina, los autores proporcionan una mejor herramienta para diseñar sistemas que sean robustos. Si estás construyendo una red de autos autónomos o un sistema de computación en la nube, no quieres que tu lógica colapse solo porque un sensor falló. Quieres un sistema que diga: "Ese sensor falló, pero veamos si el otro puede tomar el control".

El artículo demuestra que este tipo de lógica "justa" es matemáticamente posible y proporciona las reglas exactas necesarias para construirla. Sugiere que, al usar estas nuevas herramientas, podemos crear software que maneje los errores de manera más elegante, manteniendo el sistema en funcionamiento incluso cuando partes de él tropiezan. Los autores concluyen que este enfoque abre la puerta a mejores formas de verificar que los sistemas complejos y propensos a errores se comporten de manera segura, asegurando que cuando las cosas salgan mal, la computadora no se rinda, sino que siga intentándolo, de manera justa y lógica.

Resumen Técnico: Una Semántica Lógica de 3 Valores para la Elección No Determinista

Planteamiento del Problema
El artículo aborda una limitación fundamental al aplicar las lógicas estándar de tres valores (Kleene, Bochvar y McCarthy) a sistemas reactivos y no deterministas. Si bien estas lógicas modelan eficazmente la parcialidad, la indefinición y el fallo, dependen de interpretaciones deterministas de los conectivos lógicos donde cada entrada mapea a un único resultado. Esta suposición no logra capturar la realidad operacional de los sistemas concurrentes, donde la elección no determinista (por ejemplo, el operador $+$ de la álgebra de procesos) permite que diferentes ramas computacionales evolucionen de forma independiente. Los marcos existentes, como aquellos que combinan el álgebra de procesos con lógicas de tres valores, suelen tratar los errores como infecciosos (colapsando todo el sistema) o dependen de estrategias de evaluación asimétricas (como el cortocircuito de McCarthy) que imponen un sesgo direccional. En consecuencia, los formalismos lógicos actuales no pueden representar fielmente la elección no determinista genuinamente simétrica en presencia de errores, donde un fallo local en una rama no debería necesariamente suprimir las continuaciones alternativas debido a un orden de evaluación impuesto.

Metodología
Los autores proponen una formalización lógica basada en la teoría de las Matrices No Deterministas (Nmatrices). Su metodología procede a través de tres etapas principales:

Construcción de una Disyunción No Determinista Simétrica ( $\tilde{\vee}$ ):
Los autores introducen un nuevo conectivo de tres valores, $\tilde{\vee}$ , definido sobre los valores de verdad $V = \{0, 1, k\}$ (donde $k$ representa un estado de error o indefinición). Este conectivo está diseñado para ser conmutativo y para admitir resultados genuinamente no deterministas en casos mixtos.

Combina la semántica tolerante de Kleene (donde un valor indefinido en una rama no bloquea la otra) con la persistencia de error simétrica de Bochvar (donde los errores se propagan simétricamente).
Crucialmente, elimina el sesgo direccional de la lógica de McCarthy. En la tabla de verdad para $\tilde{\vee}$ , los casos $(1, k)$ y $(k, 1)$ mapean al conjunto $\{1, k\}$ , lo que indica que cuando un componente tiene éxito y el otro falla, el sistema puede resolverse no deterministicamente hacia el éxito o hacia el fallo. Esto refleja la semántica operacional de la elección en el álgebra de procesos.

Desarrollo de Cálculos de Secuentes:
El artículo desarrolla contrapartes proof-teóricas para dos interpretaciones de esta semántica:

Semántica Dinámica: Modela la resolución local donde las elecciones no deterministas se resuelven "sobre la marcha" en cada instancia del operador. El cálculo asociado, SCdB, extiende el sistema de [5] dividiendo la regla de introducción por la derecha para la disyunción en dos reglas simétricas (R4a y R4b) para reflejar la conmutatividad de $\tilde{\vee}$ .
Semántica Estática: Modela una estrategia de resolución globalmente fija (por ejemplo, un sistema centralizado con una política uniforme de manejo de errores). El cálculo estático enriquece el sistema dinámico con reglas adicionales (S1 y S2) para imponer una función de elección global coherente.

Refinamiento Determinista (Sistema de Cinco Valores):
Para proporcionar un fundamento determinista al comportamiento no determinista, los autores construyen un sistema determinista de cinco valores (SC5). Este sistema refina el único valor de error $k$ en tres tipos distintos:

$u$ (tipo Kleene): Incertidumbre suave y recuperable.
$e$ (tipo McCarthy): Fallos operacionales sensibles al orden.
$k$ (tipo Bochvar): Inconsistencias críticas y fatales.
Este sistema utiliza una disyunción no conmutativa para modelar explícitamente las estrategias de evaluación secuencial, sirviendo como un refinamiento determinista de la semántica no determinista de tres valores.

Contribuciones Clave y Resultados

Nuevo Conectivo Lógico: La contribución principal es la definición de $\tilde{\vee}$ , una disyunción no determinista y conmutativa que representa fielmente la interacción entre errores y elección no determinista sin imponer direccionalidad de evaluación.
Corrección y Completitud: Los autores demuestran que el cálculo de secuentes SCdB es correcto y completo con respecto a la semántica dinámica de la Nmatrix de tres valores ( $M^3_{BMK}$ ). Del mismo modo, se demuestra que el cálculo extendido para la semántica estática es correcto y completo.
Propiedades Metateóricas: El artículo establece que la relación de consecuencia inducida por la Nmatrix finita es finitaria y decidible, apoyándose en los resultados de Avron y Lev sobre semánticas no deterministas.
Puente Semántico: Un teorema de proyección demuestra que el sistema determinista de cinco valores ( $M^5_{BMK}$ ) actúa como un refinamiento formal del sistema dinámico de tres valores. Específicamente, una función de proyección mapea los tres tipos de error distintos ( $u, e, k$ ) del sistema de cinco valores de vuelta al único valor indeterminado $k$ del sistema de tres valores, mostrando que el aparente no determinismo al nivel de tres valores es una abstracción sólida de una taxonomía de errores graduada y determinista.

Significancia y Reivindicaciones
El artículo sostiene que las matrices no deterministas constituyen un entorno semántico natural para razonar sobre la elección simétrica en presencia de errores. La significancia de este trabajo reside en:

Formalización Lógica: Proporcionar una construcción sistemática de un conectivo no determinista que resuelve la asimetría encontrada en las combinaciones previas de lógicas de Kleene y McCarthy (por ejemplo, en [5]).
Integración con el Álgebra de Procesos: Establecer un puente preciso entre la semántica de valores múltiples no determinista y la teoría algebraica de procesos concurrentes. Los autores argumentan que la composicionalidad de su cálculo de secuentes permite la verificación modular en álgebras de procesos (como CCS), donde las pruebas de secuentes válidas sirven como certificados formales de propiedades de seguridad respecto a la propagación de errores.
Clarificación Conceptual: Al distinguir entre la resolución dinámica (local) y estática (global) del no determinismo, y al refinar esto en un marco determinista de cinco valores, el trabajo clarifica la relación entre la no clasicidad lógica y la computación operacional paso a paso.

Los autores concluyen que su marco apoya la visión de que los errores pueden tratarse como fenómenos locales que interactúan de manera no trivial con la elección no determinista, ofreciendo una base para futuras teorías ecuacionales y extensiones de álgebras de procesos como CCS.

El Problema: Lo "Perezoso" y lo "Infeccioso"

La Solución: Un Lanzamiento de Moneda Justo

Cómo lo Probaron

El "Análisis Profundo": Cinco Valores en lugar de Tres

Por Qué Esto Importa

Más como este