Back Postův korespondenční problém Czech Postsches Korrespondenzproblem German Post correspondence problem English مسئله تناظر پست Persian Problème de correspondance de Post French בעיית ההתאמה של פוסט HE Samræmingarverkefni Posts Icelandic Correspondentieprobleem van Post Dutch Posts korrespondanseproblem NN Posts korrespondanseproblem NB
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.