Siguiente: Problema de ``gramáticas ajenas'' Un nivel arriba: Irresolubilidad de problemas en Anterior: Irresolubilidad de problemas en

Reducción de problemas al problema de la parada

Como una primera sección, veamos que las computaciones terminales en una máquina de Turing dada, pueden ``realizarse'' como la intersección de dos lenguajes libres de contexto. En otras palabras, el proceso de ``correr una máquina de Turing sobre una entrada dada'' puede realizarse por dos autómatas de pila ``corriendo en paralelo''. Sea M=(Q,A,t,q₀,F) una máquina de Turing. Sea $\mbox{\bf DI}$ una computación, terminal o intermedia. Supongamos $\mbox{\bf DI}=\left\{\mbox{\it DI}_i\right\}_{i=0,\ldots,k}=\left\{\mbox{\bf y}_iq_ia_i\mbox{\bf x}_i\right\}_{i=0,\ldots,k}.$ La representación lineal de $\mbox{\bf DI}$ es la palabra

$$\mbox{\it DI}_0\bullet\mbox{\it DI}_1\bullet\cdots\bullet\mbox{\it DI}_{k-1}\bullet\mbox{\it DI}_k,$$

y la representación trastocada de $\mbox{\bf DI}$ es la palabra

$$\mbox{\it DI}_0\bullet\mbox{\it DI}_1^{\mbox{\scriptsize rev}... ...\it DI}_2\bullet\mbox{\it DI}_3^{\mbox{\scriptsize rev}}\cdots,$$

consistente de la misma palabra que en la representación lineal, salvo que las descripciones correspondientes a índices impares se escriben al revés.


Sea $L_{\rightarrow}=\left\{\mbox{\it DI}_0\bullet\mbox{\it DI}_1^{\mbox{\scriptsize... ...I's de $M$\space y }M\vdash [\mbox{\it DI}_0\rightarrow\mbox{\it DI}_1]\right\}$ el lenguaje consistente de ``inicios'' de computaciones legales en la máquina de Turing.

Proposición 3.1   $L_{\rightarrow}$ es un lenguaje libre de contexto.

Demostración: $L_{\rightarrow}$ es reconocido por un autómata de pila cuyo comportamiento es el siguiente: Dada una palabra de la forma $\mbox{\bf d}_0\bullet\mbox{\bf d}_1$,

1.

lee uno a uno los símbolos de $\mbox{\bf d}_0$, hasta llegar a ``$\bullet$'', y verifica que aparezca exactamente una vez un símbolo correspondiente a un estado, es decir, reconoce a $\mbox{\bf d}_0$ de la forma $\mbox{\bf d}_0=\mbox{\bf y}_0q_0\mbox{\bf x}_0,$

2.

reconoce a la ``parte izquierda'' de $\mbox{\bf d}_1$ como de la forma $\mbox{\bf x}_0^{\mbox{\scriptsize rev}}$, acaso tal vez difiriendo en una sola posición,

3.

verifica que donde termina $\mbox{\bf x}_0^{\mbox{\scriptsize rev}}$ aparezca la aplicación de una transición de la máquina M, y, finalmente

4.

reconoce a la ``parte derecha'' de $\mbox{\bf d}_1$ como de la forma $\mbox{\bf y}_0^{\mbox{\scriptsize rev}}$ acaso tal vez difiriendo en una sola posición.

Es claro que $L_{\rightarrow}^{\mbox{\scriptsize rev}}$ es también libre de contexto. Se tiene

$$L_{\rightarrow}^{\mbox{\scriptsize rev}}=\left\{\mbox{\it DI}... ...$ y ah\'\i\ }\mbox{\it DI}_0\rightarrow\mbox{\it DI}_1\right\}.$$

Sea $L_{\stackrel{*}{\rightarrow}}^F(\mbox{\bf x}_0)$ el lenguaje consistente de representaciones trastocadas de computaciones terminales en M que se inician con la descripción inicial $q_0\mbox{\bf x}_0$.

Proposición 3.2   $L_{\stackrel{*}{\rightarrow}}^F(\mbox{\bf x}_0)$ es la intersección de dos lenguajes libres de contexto.

Demostración: Se comprueba inmediatamente que la proposición se cumple considerando los lenguajes, evidentemente libres de contexto,

$$\begin{array}{lcrr} L_1 &=& & \left(L_{\rightarrow}\bullet\r... ...\it nil}\}\cup \mbox{\rm DI\_final}\bullet\right) \end{array}$$

Veamos a partir de este hecho que algunos problemas relativos a lenguajes libres de contexto son irresolubles.

Siguiente: Problema de ``gramáticas ajenas'' Un nivel arriba: Irresolubilidad de problemas en Anterior: Irresolubilidad de problemas en