Discusión:Problema de correspondencia de Post
Buenas,
Creo que el artículo quedaría más claro si se mencionara de forma explícita que, en la secuencia de índices i1,...ik pueden aparecer valores repetidos.
El artículo no niega que se puedan repetir pero tampoco lo afirma explícitamente en la descripción del problema. En el ejemplo final se repite el bloque 1, pero es fácil que el lector lo pase por alto y haga una suposición incorrecta.
Esto de la posibilidad de repetición es crucial, porque si el enunciado no permitiera la repetición de bloques, entonces el problema sería decidible. El algoritmo sólo tendría que probar todas las variaciones de bloques. Es un número inmenso, pero finito.
Al poderse repetir los bloques, un algoritmo de fuerza bruta tendría que explorar infinitas variaciones con repetición.
Sugiero que se mencione de forma más explícita la posibilidad de repetir bloques, ya sea en la descripción del problema, o en la solución del ejemplo.