Decidibilidad de Lenguajes y Verificación Dinámica de Algoritmos Distribuidos

El concepto de decibilidad de lenguajes es central en la teoría de la computación y las matemáticas. De manera muy general, un lenguaje es un conjunto de cadenas finitas que modela un problema
computacional a resolver, y decimos que el lenguaje es decidible si existe un algoritmo que acepta las cadenas del lenguaje, y solo esas. A lo largo de los años se han propuesto modelos de cómputodistribuidos en los que el concepto decidibilidad se extiende a ese contexto, típicamente con el objetivo de buscar algoritmos distribuidos eficientes a problemas difíciles.

En esta plática veremos una propuesta de un modelo de cómputo distribuido en la que la noción de decidibilidad captura propiedades del cómputo distintas a las propiedades en modelos anteriores. De forma concreta, la noción de decidibilidad en el modelo se relaciona con la verificación dinámica de algoritmos distribuidos. A saber, si es posible o no desarrollar algoritmos distribuidos que decidan en tiempo de ejecución si la ejecución actual de otro algoritmo distribuido es correcta.

Los resultados presentados son parte del proyecto de investigación de doctorado de Gilde Valeria Rodríguez Jiménez.