Problema de correspondencia de Post

Problema de correspondencia de Post

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 indecibilidad.

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.

u1,...,un y v1,...,vn

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

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.

Ejemplo: una instancia del problema

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

u1 u2 u3 u4 v1 v2 v3 v4
aba bbb aab bb a aaa abab babba

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

u1u4u3u1 = aba + bb + aab + aba = ababbaababa = a + babba + abab + a = v1v4v3v1

Sin embargo, si las dos listas sólo contienen u1,u2,u3 y v1,v2,v3, 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

ui
vi

Así, el ejemplo anterior se vería

aba
a
,
bbb
aaa
,
aab
abab
,
bb
babba
i = 1

i = 2

i = 3

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:

aba
a
,
bb
babba
,
aab
abab
,
aba
a
i1 = 1

i2 = 4

i3 = 3

i4 = 1

Véase también


Wikimedia foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Mira otros diccionarios:

  • 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 indecibilidad.… …   Enciclopedia Universal

  • Hannah Arendt — en una ilustración de Aretz para el sello de la serie Mujeres de la Historia alemana. Hannah Arendt, nacida como Johanna Arendt, (Linden Limmer, hoy …   Wikipedia Español

  • Carl Gustav Jung — «Jung» redirige aquí. Para otras acepciones, véase Jung (desambiguación). Carl Gustav Jung …   Wikipedia Español

  • Prejuicio cognitivo — Saltar a navegación, búsqueda El hombre en el centro ha cometido un error en sus pasos de baile, y choca contra la mujer, que se enoja y los demás murmuran. Sólo las personas que vieron la miniserie Orgullo y prejuicio (1995) pueden entender el… …   Wikipedia Español

  • Anexo:Sesgos cognitivos — El hombre en el centro ha cometido un error en sus pasos de baile, y choca contra la mujer, que se enoja y los demás murmuran. En la obra de Jane Austen Orgullo y prejuicio (1813) se muestra claramente el prejuicio de clases sociales y cómo el… …   Wikipedia Español

  • Alfred Russel Wallace — Alfred Russel Wallace …   Wikipedia Español

  • Luigi Pasinetti — «Pasinetti» redirige aquí. Para otras acepciones, véase Pasinetti (desambiguación). Luigi Pasinetti. Luigi L. Pasinetti (12 de Septiembre de 1930) es un economista italiano de la escuela de economía postkeynesiana. Pasinetti es considerado el… …   Wikipedia Español

  • Ciencia — La ciencia (del latín scientia conocimiento ) es el conjunto de conocimientos sistemáticamente estructurados, y susceptibles de ser articulados unos con otros. El árbol de la ciencia. Interpretación bíblica Contenido …   Wikipedia Español

  • Praga — Praha Praga …   Wikipedia Español

  • James Joyce — James Joyce …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”