Siguiente: Problema de complemento libre Un nivel arriba: Irresolubilidad de problemas en Anterior: Problema de regularidad contenida

Algunos otros problemas irresolubles

Recordemos el Lema de Bombeo para GLC's: Sea L un LLC. Existe una constante $n\in I\!\!N$ tal que si $\mbox{\bf z}\in L$ es una palabra de longitud al menos n entonces la palabra $\mbox{\bf z}$ se puede descomponer como $\mbox{\bf z}=\mbox{\bf z}_1\mbox{\bf z}_2\mbox{\bf z}_3\mbox{\bf z}_4\mbox{\bf z}_5$, de manera que $\mbox{\rm long}(\mbox{\bf z}_2)+\mbox{\rm long}(\mbox{\bf z}_4)\geq 1$, $\mbox{\rm long}(\mbox{\bf z}_2\mbox{\bf z}_3\mbox{\bf z}_4)\leq n$, y $\forall k\in I\!\!N:\ \mbox{\bf z}_1\mbox{\bf z}_2^k\mbox{\bf z}_3\mbox{\bf z}_4^k\mbox{\bf z}_5 \in L$.


Ahora bien toda máquina de Turing es equivalente, mediante la adición de estados redundantes, a una máquina de Turing tal que toda computación terminal involucra al menos tres DI's. De aquí se tiene el

Lema 3.1   Sea M una máquina de Turing. Sea C_M el conjunto de computaciones terminales en M. Entonces

$$C_M\mbox{\rm es un LLC }\ \Leftrightarrow\ L(M)\mbox{\rm es un lenguaje finito.}$$

Demostración: $\Rightarrow)$ Si L(M) fuera infinito y C_M libre de contexto se contradiría al Lema de Bombeo. $\Leftarrow)$ Es evidente, pues todo lenguaje finito es libre de contexto.