Problema de correspondencia de Post

El Problema de Correspondencia de Post es un problema de decisión indecidible que fue propuesto por Emil Post. Por ser más sencillo que el Problema de parada y que el Entscheidungsproblem, resulta útil para realizar pruebas de indecidilidad.

Informalmente, el problema puede ser descrito como sigue: Dado un diccionario bilingüe que contiene pares de frases, es decir, listas de palabras, que significan lo mismo, decidir si existe una frase que significa lo mismo en ambos lenguajes.

Definición del problema

La entrada del problema está formada por dos listas finitas.

y

de palabras sobre un alfabeto dado Σ que contiene al menos dos símbolos. Una solución a este problema es una secuencia de índices , tales que

.

El problema de decisión consiste en saber si existe una solución para el problema planteado.

Other Languages