¿Por qué es indecidible si dos transductores de estado finito son equivalentes?

Question

Según la página de Wikipedia sobre transductores de estado finito es indecidible si dos transductores de estado finito son equivalentes. Este resultado me parece sorprendente, ya que es decidible si dos autómatas de estado finito son equivalentes entre sí.

Lamentablemente, la Wikipedia no proporciona ninguna cita que justifique este resultado. ¿Alguien conoce una prueba de este resultado? O bien, si el artículo es incorrecto, ¿alguien conoce un algoritmo que pueda utilizarse para demostrar la equivalencia?

Gracias.

Answer 1

Esta página web de la versión en línea de Introducción a la teoría de la computación de Eitan Gurari, muestra que el problema de equivalencia para transductores de estado finito es indecidible por reducción a partir del Problema de la Correspondencia Posterior, cuya indecidibilidad se muestra en la misma página; cita

Griffiths, T. (1968). "The unsolvability of the equivalence problem for $\Lambda$ -free nondeterministic generalized machines", Journal of the Association for Computing Machinery 15, 409-413,

para el resultado.

El propio Gurari demostró que el problema de equivalencia es decidible para transductores deterministas:

El problema de equivalencia de los transductores secuenciales bidireccionales deterministas es decidible. SIAM J. Comput. , 11(3):448-452, 1982.

Aparentemente, la dificultad radica en que algunos transductores de estado finito no deterministas no pueden reducirse a deterministas.

Answer 2

Para complementar la respuesta de Brian, tal vez quieras ver El problema de equivalencia de los autómatas finitos de varias cintas donde los autores dan un algoritmo para decidir si dos transductores deterministas son equivalentes. La clave es que se puede decidir si dos autómatas son equivalentes con respecto a las multiplicidades (es decir, cuántas veces se acepta la palabra).

Esto está muy relacionado con autómatas probabilísticos cuyo algoritmo de equivalencia se dio en Un algoritmo de tiempo polinómico para la equivalencia de autómatas probabilísticos . En este contexto, la cuestión es si dos autómatas aceptan la palabra con la misma probabilidad.

Se puede generalizar esto para algunos autómatas ponderados, sin perder la decidibilidad (ver aquí para ver bonitas diapositivas con ejemplos). Por lo tanto, se podrían transformar los autómatas deterministas (de varias cintas) en una versión ponderada, de forma que la palabra se acepte si y sólo si tiene (en algún semirrecordatorio) un peso 1 (uno), y después simplemente utilizar el algoritmo anterior. Sin embargo, tenga en cuenta que este resultado es bastante frágil, incluso añadiendo $\varepsilon$ -edges haría esto indecidible.

Espero que esto ayude ;-)