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.
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.
Las dos listas siguientes representan una instancia del problema de correspondencia de Post: Una solución al problema es la secuencia 1, 4, 3, 1 dado que Sin embargo, si las dos listas sólo contienen
Una solución al problema anterior corresponde a: