Problema de correspondencia posterior

Post Correspondence Problem es un popular problema indecidible que fue presentado por Emil Leon Post en 1946. Es más simple que Halting Problem. En este problema tenemos N número de fichas de dominó (fichas). El objetivo es organizar las fichas en tal orden que la string formada por los numeradores sea la misma que la string formada por los denominadores. En palabras simples, supongamos que tenemos dos listas que contienen N palabras, el objetivo es descubrir la concatenación de estas palabras en alguna secuencia de modo que ambas listas produzcan el mismo resultado. Tratemos de entender esto tomando dos listas A y B

A=[aa, bb, abb] and B=[aab, ba, b] 

Ahora, para la secuencia 1, 2, 1, 3, la primera lista producirá aabbaaabb y la segunda lista producirá la misma string aabbaaabb. Entonces, la solución a este PCP se convierte en 1, 2, 1, 3. Los problemas posteriores a la correspondencia se pueden representar de dos maneras: 

1. Forma de Domino: 2. Forma de tabla:  
Consideremos los siguientes ejemplos. Ejemplo-1: Explicación –

• Paso 1: Comenzaremos con el mosaico en el que el numerador y el denominador comienzan con el mismo número, por lo que podemos comenzar con 1 o 2. Vayamos con el segundo mosaico, la string formada por el numerador-10111, la string formada por el denominador es 10.
• Paso 2: Necesitamos 1 en el denominador para que coincida con 1 en el numerador, así que iremos con el primer mosaico, la string hecha por el numerador es 10111 1, la string hecha por el denominador es 10 111.
• Paso 3: Hay 1 adicional en el numerador para que coincida con este 1, agregaremos la primera ficha en secuencia, la string hecha por el numerador ahora es 10111 1 1, la string hecha por el denominador es 10 111 111.
• Paso 4: ahora hay 1 extra en el denominador para que coincida, agregaremos el tercer mosaico, la string hecha por el numerador es 10111 1 1 10, la string hecha por el denominador es 10 111 111 0.

Final Solution - 2 1 1 3
String made by numerators: 101111110
String made by denominators: 101111110 

• Como puede ver, las strings son iguales.

Ejemplo-2: Explicación –

• Paso 1: Comenzaremos desde el mosaico 1 ya que es nuestra única opción, la string hecha por el numerador es 100, la string hecha por el denominador es 1.
• Paso 2: tenemos 00 extra en el numerador, para equilibrar esta única forma es agregar el mosaico 3 a la secuencia, la string hecha por el numerador es 100 1, la string hecha por el denominador es 1 00.
• Paso 3: Hay 1 adicional en el numerador para equilibrar, podemos agregar el mosaico 1 o el mosaico 2 . Intentemos sumar el mosaico 1 primero, la string formada por el numerador es 100 1 100, la string formada por el denominador es 1 00 1.
• Paso 4: hay 100 adicionales en el numerador, para equilibrar esto, podemos agregar el primer mosaico nuevamente, la string hecha por el numerador es 100 1 100 100, la string hecha por el denominador es 1 00 1 1 1. El sexto dígito en la string del numerador es 0 que es diferente del sexto dígito en la string hecha por denominador que es 1.

Podemos probar combinaciones ilimitadas como la de arriba pero ninguna combinación nos llevará a la solución, por lo que este problema no tiene solución. Indecidibilidad del problema de correspondencia posterior: como teorema dice que PCP es indecidible. Es decir, no existe un algoritmo particular que determine si algún Sistema de Correos por Correspondencia tiene solución o no. Prueba: ya sabemos sobre la indecidibilidad de la máquina de Turing. Si somos capaces de reducir la máquina de Turing a PCP, probaremos que el PCP también es indecidible. Considere la máquina de Turing M para simular la string de entrada de PCP w puede representarse como . Si hay una coincidencia en la string de entrada w, entonces la máquina de Turing M se detiene en el estado de aceptación. Este estado de parada de la máquina de Turing es un problema de aceptación A _TM. Sabemos que el problema de aceptación A _TM es indecidible. Por lo tanto, el problema del PCP también es indecidible. Para forzar la simulación de M, hacemos 2 modificaciones a Turing Machine M y un cambio a nuestro problema PCP.

1. M en la entrada w nunca puede intentar mover el cabezal de la cinta más allá del extremo izquierdo de la cinta de entrada.
2. Si la entrada es una string vacía €, usamos _.
3. El problema de PCP comienza a coincidir con el primer dominó [u1/v1] Esto se denomina problema de PCP modificado.

MPCP = {[D] | D is instance of PCP starts with first domino} 

Pasos de construcción –

1. Coloque [# / (#q0w1w2..wn#)] en D como primer dominó, donde la instancia de D es MPCP. Se obtiene una coincidencia parcial en el primer dominó es # en una cara es el mismo #símbolo en la otra cara.
2. Las funciones de transición para la Máquina de Turing M pueden tener movimientos Izquierda L, Derecha R. Para cada x, yz en alfabetos de cinta y q, r en Q donde q no es igual a q _rechazar . Si transición (q, x) = (r, y, R) coloque dominó [qx / by] en D y transición (q, x) = (r, y, L) coloque dominó [zqx / rzy] en D.
3. Para cada alfabeto de cinta x, coloque [x / x] en D. Para marcar la separación de cada configuración, coloque [# / #] y [# / _#] en D.
4. Para leer los alfabetos de entrada x incluso después de que Turing Machine esté aceptando el estado, coloque [xqa / qa] y [qax / qa] y [qa# / #] en D. Estos pasos concluyen la construcción de D.

Dado que esta instancia de MPCP, necesitamos convertir esto a PCP. Entonces, para convertir a D, consideramos a continuación el dominó y la coincidencia de strings. 

Conversión de MPCP a PCP: Sea u = u1, u2, …, un cualquier string de longitud de entrada n y modifique estas strings como

$u = *u1*u2*u3* …*un
u$ = u1* u2* u3* … un*
$u$ = * u1* u2* u3* ... un* 

Sea D un conjunto de fichas de dominó de dos caras,

D = {[u1 / v1], [u2 / v2], [u3 / v3], ..., [un / vn]} and {[$u1 / $v1$], [$u2 / v2$], ..., [*_ / _]} 

De la colección de dominó anterior, pudimos ver que solo el dominó tiene un comienzo de coincidencia parcial con [$u1 / $v1$] y para colocar el marcador al final de las entradas [*_ / _]. Por lo tanto, podemos evitar indicar que el requisito explícito de dominó debe comenzar con el primer dominó. Si el número de configuraciones de la máquina de Turing no se encuentra dentro del valor de qng ⁿ , entonces la máquina de Turing está en estado de bucle. No se detiene.