Siguiente: Una aplicación de PCP Un nivel arriba: Problema de la correspondencia Anterior: Problema de la correspondencia

Presentación del Problema de Post

Sea A un alfabeto finito y sea A^* su diccionario. El problema de la correspondencia de Post (PCP) se define como sigue:


Instancia:

Solución:






Ejemplos Consideremos

$$\begin{array}{lcl} \mbox{\bf X}={\left[\begin{array}{l} \mb... ...11 \\ 0 \\ 1 \\ 1110 \\ 11101 \end{array}\right]} \end{array}$$

Para $\mbox{\bf I}=[5,2,3,3,6]$ se tiene

$$\mbox{\bf x}_5\mbox{\bf x}_2\mbox{\bf x}_3\mbox{\bf x}_3\mbox... ...bf y}_5\mbox{\bf y}_2\mbox{\bf y}_3\mbox{\bf y}_3\mbox{\bf y}_6$$

pues

$$\begin{eqnarray*}10110111011110111110 &=& 101.10.11101.11101.11110 \\ &=& 1.01101.11011.11011.1110 \end{eqnarray*}$$

En cambio para

$$\begin{array}{lclll} \mbox{\bf X}={\left[\mbox{\bf x}_1,\mbo... ...}_2,\mbox{\bf y}_3\right]}&=&{[} 00 & 1 & 101{]} \end{array}$$

el PCP no tiene solución alguna. (¡Revísese!)


El problema de la correspondencia de Post modificado (PCPM) coincide con el anterior salvo en que en este último se impone la exigencia de que la cadena común formada comience con las primeras palabras en las listas dadas:


Instancia:

Solución:

Proposición 2.1   Si PCP fuera efectivamente resoluble entonces PCPM lo sería también.

Demostración: Traduciremos toda instancia $(\mbox{\bf X}^M,\mbox{\bf Y}^M)$ de PCPM, con n palabras en cada lista, a una instancia $(\mbox{\bf X},\mbox{\bf Y})$ de PCP de manera que la instancia traducida posea una solución cuando y sólo cuando la instancia original también posea una correspondiente solución. Al traducir utilizaremos dos nuevos símbolos separadores `` $\circ,\bullet$''. Ilustraremos el procedimiento con el ejemplo anterior con solución $\mbox{\bf I}=[5,2,3,3,6]$. Para partir de una solución de PCPM, intercambiaremos las palabras primera y quinta en cada conjunto de palabras:

$$\begin{array}{lcl} \mbox{\bf X}^M={\left[\begin{array}{l} 1... ... \\ 0 \\ 101 \\ 1110 \\ 11101 \end{array}\right]} \end{array}$$

La solución es pues $\mbox{\bf I}=[1,2,3,3,6]$. Para hacer la conversión, cambiaremos primero a las listas de palabras $\mbox{\bf X}^M,\mbox{\bf Y}^M$, después introduciremos nuevas palabras iniciales y nuevas palabras terminales.

• Construcción de $\mbox{\bf X}$: $\mbox{\bf X}$ se obtiene de $\mbox{\bf X}^M$ sustituyendo cada símbolo a de A por $a\circ$.
  
  $$\mbox{\bf X}={\left[\begin{array}{l} 1\circ 0\circ 1\circ \\... ...\circ \\ 0\circ 1\circ 1\circ 0\circ 1\circ \end{array}\right]}$$
  
  

• Construcción de $\mbox{\bf Y}$: $\mbox{\bf Y}$ se obtiene de $\mbox{\bf Y}^M$ sustituyendo cada símbolo a de A por $\circ a$.
  
  $$\mbox{\bf Y}={\left[\begin{array}{l} \circ 1 \\ \circ 0\circ... ...0 \\ \circ 1\circ 1\circ 1\circ 0\circ 1 \end{array}\right]}$$
  
  

• Construcción de palabras iniciales: Hagamos $\mbox{\bf x}_0=\circ\mbox{\bf x}_1$ e $\mbox{\bf y}_0=\mbox{\bf y}_1$.
  
  $$\begin{eqnarray*}\mbox{\bf x}_0 &=&\circ 1\circ 0\circ 1\circ \\ \mbox{\bf y}_0 &=&\circ 1 \end{eqnarray*}$$
  
  
• Construcción de palabras terminales: Hagamos $\mbox{\bf x}_{n+1}=\bullet$ e $\mbox{\bf y}_{n+1}=\circ\bullet$.
  
  $$\begin{eqnarray*}\mbox{\bf x}_8 &=&\bullet \\ \mbox{\bf y}_8 &=&\circ\bullet \end{eqnarray*}$$
  
  

Veamos ahora cómo corresponden soluciones de PCPM a soluciones de PCP y viceversa.

• Una solución de $(\mbox{\bf X}^M,\mbox{\bf Y}^M)$ en PCPM da una solución de $(\mbox{\bf X},\mbox{\bf Y})$ en PCP: Si $\mbox{\bf I}^M=[1,i_1,\ldots,i_k]$ es una solución de PCPM entonces $\mbox{\bf I}=[0,i_1,\ldots,i_k,n+1]$ es solución de PCP. En el ejemplo mostrado, la palabra común dada por la solución $\mbox{\bf I}=[0,2,3,3,6,8],$ inducida a su vez por la solución $\mbox{\bf I}^M=[1,2,3,3,6]$ es
  
  $$\circ 1\circ 0\circ 1\circ 1\circ 0\circ 1\circ 1\circ 1\circ... ... 1\circ 0\circ 1\circ 1\circ 1\circ 1\circ 1\circ 0\circ\bullet$$
  
  

• Una solución de $(\mbox{\bf X},\mbox{\bf Y})$ en PCP da una solución de $(\mbox{\bf X}^M,\mbox{\bf Y}^M)$ en PCPM: Si $\mbox{\bf I}=[i_1,i_2\ldots,i_{k-1},i_k]$ es una solución de PCP entonces necesariamente i₁=0 e i_k=n+1, pues ésta es la única manera de que ``empaten'' las marcas extremas $\circ,\bullet$; es decir, la palabra común ha de comenzar con las palabras iniciales y ha de terminar con las terminales. Sea i_j el mínimo índice tal que i_j=n+1. Evidentemente $\mbox{\bf I}'=[i_1,i_2\ldots,i_{j-1},i_j]$ también es solución de PCP. Se ve de manera directa que $\mbox{\bf I}^M=[1,i_2,\ldots,i_{j-1}]$ es solución de PCPM.

Teorema 2.1   PCP es irresoluble.

Demostración: Veremos que PCPM no puede resolverse efectivamente. Para esto veremos cómo una instancia del Problema de la Parada en máquinas de Turing (PPmT) se reduce algorítmicamente a una instancia de PCPM de manera que la instancia a reducirse ha de poseer una solución, es decir, se reconocerá que la máquina ``instancia'' se parará a partir del contenido inicial ``instancia'', en PPmT si y sólo si la correspondiente instancia ya reducida posee una solución para PCPM. Siendo entonces PPmT reducible a PCPM se sigue inmediatamente que este último problema no puede ser resoluble pues si lo fuera, PCmT también lo sería, lo cual es imposible. Sea pues $(M,\mbox{\bf w})$ una instancia de PPmT: M es una mT y $\mbox{\bf w}$ es una entrada para M. Sea $\mbox{\it AQ}= A\cup Q\cup\{\bullet\}$ el alfabeto consistente de los símbolos y los estados de M, y de un símbolo para indicar extremos de DI's. Construiremos dos sucesiones de palabras $\mbox{\bf X},\mbox{\bf Y}\subset \mbox{\it AQ}^*$ tales que $(\mbox{\bf X},\mbox{\bf Y})$ posee solución en PCP si y sólo si $M(\mbox{\bf w})\downarrow$ y en tal caso una solución de PCPM ha de consistir, propiamente, de una computación terminal que transforma la DI inicial $q_0\mbox{\bf x}$ en alguna DI final. Las construcciones de ambas listas $\mbox{\bf X},\mbox{\bf Y}$ se hacen por etapas. En las tablas 5.1-5.3 quedan mostradas las palabras formadas para sendas listas $\mbox{\bf X},\mbox{\bf Y}$ divididas por grupos: en el primer grupo presentamos partículas iniciales y las relativas al alfabeto de la m.T., en el segundo grupo aparecen las que codifican el funcionamiento de la m.T. y en el tercer grupo se enlista a las partículas terminales.

  

Table 5.1: Grupo I: Parejas iniciales y de símbolos en la m. T.

  

Table 5.2: Grupo II: Parejas de transiciones.

  

Table 5.3: Grupo III: Parejas de estados finales y DI's terminales.

Veamos que una solución de PPmT da una solución para PCPM. Se dice que una pareja $(C,D)\in\left(\mbox{\it AQ}^*\right)^2$ es una solución parcial de PCPM si

• C es un prefijo de D, y
• C y D son yuxtaposiciones de correspondientes cadenas en las listas $\mbox{\bf X}$ y $\mbox{\bf Y}$, es decir, si $C=\mbox{\bf x}_{i_1}\ldots\mbox{\bf x}_{i_k}$ entonces $D=\mbox{\bf y}_{i_1}\ldots\mbox{\bf y}_{i_k}E$, donde $E\in\mbox{\it AQ}^*$. En tal caso, la partícula E es el residuo de la solución parcial (C,D).

Se ve que las siguientes dos proposiciones son equivalentes:

1.

La sucesión de DI's $\mbox{\bf DI}=\left\{\mbox{\it DI}_i=\mbox{\boldmath$\alpha$ }_iq_ia_i\mbox{\boldmath$\beta$ }_i\right\}_{i=0,\ldots,k}$ es una computación, intermedia o terminal, de longitud k+1 en la m. T. M, es decir $\forall i<k:M\vdash \mbox{\it DI}_i\rightarrow\mbox{\it DI}_{i+1}$.

2.

Si

$$\begin{eqnarray*}C_k &=&q_0\mbox{\bf w}\bullet\mbox{\boldmath$\alpha$ }_1q_1a_1\... ...oldmath$\alpha$ }_{k}q_{k}a_{k}\mbox{\boldmath$\beta$ }_{k} E_k \end{eqnarray*}$$

entonces (C_k,D_k) es una solución parcial de PCPM.

Las dos implicaciones a demostrar se prueban por inducción en k. Ahora, con la notación anterior, observamos que la solución parcial de la forma (C_k,D_k) más pequeña corresponde a cuando E_k es la palabra vacía. También observamos que si no aparecen palabras del grupo III, entonces en toda solución parcial (C_k,D_k), la longitud de D_k es estrictamente mayor que la de C_k. Por tanto, se tendrá una solución a PCPM si y sólo si se tiene una computación terminal en la máquina dada.
Siguiente: Una aplicación de PCP Un nivel arriba: Problema de la correspondencia Anterior: Problema de la correspondencia