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.

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

${\displaystyle u_{1},...,u_{n}}$ y ${\displaystyle v_{1},...,v_{n}}$

de palabras sobre un alfabeto dado Σ que contiene al menos dos símbolos. Una solución a este problema es una secuencia de índices ${\displaystyle i_{1},...,i_{k},1\leq i_{j}\leq n}$, tales que

${\displaystyle u_{i_{1}}...u_{i_{k}}=v_{i_{1}}...v_{i_{k}}}$.

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

Las dos listas siguientes representan una instancia del problema de correspondencia de Post:

${\displaystyle u_{1}}$	${\displaystyle u_{2}}$	${\displaystyle u_{3}}$	${\displaystyle u_{4}}$	${\displaystyle v_{1}}$	${\displaystyle v_{2}}$	${\displaystyle v_{3}}$	${\displaystyle v_{4}}$
${\displaystyle aba}$	${\displaystyle bbb}$	${\displaystyle aab}$	${\displaystyle bb}$	${\displaystyle a}$	${\displaystyle aaa}$	${\displaystyle abab}$	${\displaystyle babba}$

Una solución al problema es la secuencia 1, 4, 3, 1 dado que

${\displaystyle u_{1}u_{4}u_{3}u_{1}=aba+bb+aab+aba=ababbaababa=a+babba+abab+a=v_{1}v_{4}v_{3}v_{1}}$

Sin embargo, si las dos listas sólo contienen ${\displaystyle u_{1},u_{2},u_{3}}$ y ${\displaystyle v_{1},v_{2},v_{3}}$, entonces ya no hay solución.

Una manera práctica de ver una instancia de un problema de correspondencia de Post es como una colección de bloques de la forma

${\displaystyle u_{i}}$

${\displaystyle v_{i}}$

Así, el ejemplo anterior se vería

${\displaystyle aba}$ ${\displaystyle a}$	,	${\displaystyle bbb}$ ${\displaystyle aaa}$	,	${\displaystyle aab}$ ${\displaystyle abab}$	,	${\displaystyle bb}$ ${\displaystyle babba}$
${\displaystyle i=1}$		${\displaystyle i=2}$		${\displaystyle i=3}$		${\displaystyle i=4}$

Una solución corresponde a una forma de colocar bloques, los unos junto a los otros de manera que la cadena en las celdas de más arriba corresponden a las cadenas de las celdas inferiores. Una solución al problema anterior corresponde a:

${\displaystyle aba}$ ${\displaystyle a}$	,	${\displaystyle bb}$ ${\displaystyle babba}$	,	${\displaystyle aab}$ ${\displaystyle abab}$	,	${\displaystyle aba}$ ${\displaystyle a}$
${\displaystyle i_{1}=1}$		${\displaystyle i_{2}=4}$		${\displaystyle i_{3}=3}$		${\displaystyle i_{4}=1}$

• Máquina de Post