Siguiente: Problema de equivalencia (PE) Un nivel arriba: Reducción de problemas al Anterior: Problema de ``gramáticas ajenas''

Problema de totalidad (PT)

Instancia:

Solución:

Proposición 3.4   PT es irresoluble.

Demostración: Puede verse que el lenguaje complementario a las representaciones trastocadas de computaciones en la máquina de Turing es libre de contexto. En efecto, una palabra $\sigma$ está en el lenguaje complementario si se cumple alguna de las condiciones siguientes:

1.

No es de la forma $\mbox{\bf DI}=\left\{\left(\mbox{\it DI}_i\right)^{(-1)^i}\right\}_{i=0,\ldots,... ...left(\mbox{\bf y}_iq_ia_i\mbox{\bf x}_i\right)^{(-1)^i}\right\}_{i=0,\ldots,k},$ donde $\tau^{1}=\tau$ y $\tau^{-1}=\tau^{\mbox{\scriptsize rev}}$.

2.

Siendo de la forma $\mbox{\bf DI}$, se tiene que la primera $\mbox{\bf y}_0q_0a_0\mbox{\bf x}_0$ no es inicial (es decir, el q₀ que ahí aparece no es el estado inicial de la máquina de Turing).

3.

Siendo de la forma $\mbox{\bf DI}$, se tiene que la última $\mbox{\bf y}_kq_ka_k\mbox{\bf x}_k$ no es terminal, es decir, $q_k\not\in F$.

4.

Para alguna i par se tiene $\not\vdash \mbox{\bf y}_iq_ia_i\mbox{\bf x}_i \rightarrow \left(\mbox{\bf y}_{i+1}q_{i+1}a_{i+1}\mbox{\bf x}_{i+1}\right)^{\mbox{\scriptsize rev}}$.

5.

Para alguna i impar se tiene $\not\vdash \left(\mbox{\bf y}_iq_ia_i\mbox{\bf x}_i\right)^{\mbox{\scriptsize rev}} \rightarrow \mbox{\bf y}_{i+1}q_{i+1}a_{i+1}\mbox{\bf x}_{i+1}$.

Cada una de las tres primeras condiciones define a un lenguaje regular, y por tanto, libre de contexto. La revisión de las condiciones 4. y 5. puede hacerse mediante sendos autómatas de pila y por tanto éstas determinan lenguajes libres de contexto. Así pues, el lenguaje complementario es libre de contexto como unión de lenguajes libres de contexto. Si pudiéramos reconocer que este lenguaje es total podríamos reconocer que no hay computación terminal para una entrada dada de la máquina de Turing. Esto también resolvería el Problema de la Parada.
Siguiente: Problema de equivalencia (PE) Un nivel arriba: Reducción de problemas al Anterior: Problema de ``gramáticas ajenas''