Estoy buscando una explicación sobre cómo se podría probar que dos modelos de cálculo son equivalentes. He estado leyendo libros sobre el tema, excepto que se omiten las pruebas de equivalencia. Tengo una idea básica sobre lo que significa que dos modelos de computación sean equivalentes (la vista de autómatas: si aceptan los mismos idiomas). ¿Hay otras formas de pensar acerca de la equivalencia? Si pudiera ayudarme a comprender cómo demostrar que el modelo de máquina de Turing es equivalente al cálculo lambda, eso sería suficiente.
proof-techniques
computation-models
simulation
saadtaame
fuente
fuente
Respuestas:
Muestras que cualquiera de los modelos puede simular al otro, que tiene una máquina en el modelo A, muestra que hay una máquina en el modelo B que calcula la misma función. Tenga en cuenta que esta simulación no tiene que ser computable (pero generalmente lo es).
Considere, por ejemplo, autómatas pushdown con dos pilas (2-PDA). En otra pregunta , se resumen las simulaciones en ambas direcciones. Si hiciera esto formalmente, tomaría una máquina de Turing general (una tupla) y construiría explícitamente cuál sería el 2-PDA correspondiente, y viceversa.
Formalmente, tal simulación puede verse así. Dejar
ser una máquina de Turing (con una cinta). Luego,
[ fuente ]
Queda por demostrar queUNAMETRO entra en un estado final en x ∈ Σ∗yo si y solo si METRO lo hace Esto es bastante claro por construcción; formalmente, tienes que traducir aceptando carreras enMETRO en aceptar carreras en UNAMETRO y viceversa.
fuente
Al comienzo de los sistemas de comunicación y móviles: el cálculo Pi de Robin Milner, hay una introducción sobre los autómatas y cómo pueden simularse entre sí para que no puedan distinguirse: Bisimulación . (cf Bisimulación en wikipedia)
No recuerdo bien, debería volver a leer el capítulo, pero hubo un problema con la simulación y la bisimulación que los hizo insuficientes para las equivalencias computacionales.
Así, Robin Milner presenta su Pi-Calculus y lo expone para el resto del libro.
En última instancia, en su último libro The Space and Motion of Communicating Agents , podría echar un vistazo a Bigraphs de Robin Milner. Pueden modelar autómatas, redes de Petri, cálculo de Pi y otras metodologías computacionales.
fuente
Hasta donde yo sé, la única (o al menos más común) forma de hacerlo es comparar los idiomas que aceptan las máquinas / modelos. Ese es el objetivo de la teoría de Autómatas: toma el concepto vago de un problema o algoritmo y lo convierte en un conjunto matemático concreto (es decir, un lenguaje) sobre el que podemos razonar.
La manera más fácil de hacer esto es, dada una máquina / función arbitraria de un modelo, construir una máquina a partir del segundo modelo que calcule el mismo lenguaje. Lo más probable es que use inducción en la longitud de la expresión, estados en la máquina, reglas en la gramática, etc.
No he visto esto hecho con Lambda y TM (aunque estoy 99% seguro de que es posible), pero definitivamente he visto este tipo de cosas para probar la equivalencia de NFA y expresiones regulares. Primero muestra un NFA que puede aceptar cualquier átomo, luego, usando la inducción, crea NFA que acepta la unión / concatenación / estrella de Kleene de cualquier NFA más pequeño.
Luego haces lo contrario, para encontrar un RE para cualquier NFA.
fuente