Problema de correspondencia de Post

De Wikipedia, la enciclopedia libre

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

[editar] Definición del problema

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

u 1,..., u n

and

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

[editar] Ejemplo: una instancia del problema

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

$u 1$	$u 2$	$u 3$	$u 4$	$v 1$	$v 2$	$v 3$	$v 4$
$a b a$	$b b b$	$a a b$	$b b$	$a$	$a a a$	$a b a b$	$b a b b a$

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

u 1 u 4 u 3 u 1 = a b a + b b + a a b + a b a = a b a b b a a b a b a = a + b a b b a + a b a b + a = v 1 v 4 v 3 v 1

Sin embargo, si las dos listas sólo contienen $u 1, u 2, u 3$ y $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

u i

v i

Así, el ejemplo anterior se vería

a b a

a

b b b

a a a

a a b

a b a b

b b

b a b b a

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:

a b a

a

b b

b a b b a

a a b

a b a b

a b a

a

i 1 = 1

i 2 = 4

i 3 = 3

i 4 = 1

[editar] Véase también

Máquina de Post

Categoría: Máquinas de Turing

See also ebooksgratis.com: no banners, no cookies, totally FREE.

Problema de correspondencia de Post

De Wikipedia, la enciclopedia libre

[editar] Definición del problema

[editar] Ejemplo: una instancia del problema

[editar] Véase también

Views

Navegación

Buscar

En otros idiomas