Lenguajes recursivos (LRC) y recursivamente enumerables (LRE)

Es decir, los LRE son la clase de lenguajes que aceptan las máquinas de Turing.

Los lenguajes LRC garantizan que la MT que los acepta terminará siempre y nunca entrará en un bucle infinito.

Hay lenguajes que no son LRE. La demostración es compleja, puesto que todos los lenguajes descritos de forma algorítmica son aceptados por MT.

Decidibilidad

Ya hemos visto que una función $f$ es computable en un dominio si existe una MT que computa el valor de $f$ para todos los argumentos del dominio.

Si el resultado de la computación de un problema es Sí / No, se habla de decidibilidad / indecidibilidad (respectivamente).

Problema de la parada

Sea $M$ una MT cualquiera, descrita por la cadena $w_M$, y sea $w$ una cadena de entrada a la máquina $M$.

Una solución al problema de la parada sería una máquina de Turing universal $H$ en la que, para cualquier máquina $M$ (cualesquiera $w_M$ y $w$), se ejecuta una computación para determinar si $M$ entra en un bucle infinito o no:

• $q_0 w_M w \vdash^* x_1 q_y x_2$, si $M$ aplicada a $w$ se para
• $q_0 w_M w \vdash^* x_1 q_n x_2$, si $M$ aplicada a $w$ no se para

$q_y$ el es estado final representando la respuesta Sí, se para y $q_n$ de la respuesta No, no se para, para la máquina $H$.

No existe ninguna MT $H$ que se comporte como se require para el problema de la parada: es un problema indecidible. De lo contrario, entonces todos los LRE sería LRC.

Complejidad computacional

Para determinar la complejidad computacional de cualquier algoritmo:

• Usaremos máquinas de Turing
• El tamaño del problema será $n$
• Interesa saber cuánto aumenta el tiempo al incrementar $n$

Es decir, que una computación o MT tiene complejidad temporal de $T(n)$ si acepta o termina en menos de esos movimientos sea cual sea la entrada. Generalmente, no nos interesará el tiempo exacto, pero sí el orden de magnitud.

Desde el punto de vista de la decidibilidad, todas las MT son equivalentes; pero desde el punto de vista de la complejidad no. Por ejemplo, para reconocer el lenguaje $L = \set{a^n b^n | n \ge 1}$:

• MT estándar: $O(n^2)$
• MT con dos cintas: $O(n)$

Complejidades P y NP

• Un lenguaje $L$ pertenece a la clase $\operatorname{TD}(T(n))$ si hay una MT multicinta determinista que acepta $L$ en tiempo $T(n)$.
• Un lenguaje $L$ pertenece a la clase $\operatorname{TND}(T(n))$ si hay una MT multicinta no determinista que acepta $L$ en tiempo $T(n)$.

Sabemos que $P \subseteq NP$, pero…

Este es un problema del milenio, todavía sin resolver.

• Si $L_1$ es reducible en tiempo polinómico a $L_2$ y $L_2 \in P$, entonces $L_1 \in P$.
• De igual forma, si $L_2 \in NP$, entonces $L_1 \in NP$.

Es decir, que es posible transformar un problema (o computación, representado como una cadena de un lenguaje) a otro por una MT en tiempo polinómico. Si uno de estos problemas es de la clase $P$ o $NP$, entonces el otro también lo será, dado que se puede convertir de uno a otro sin un gran coste adicional.

Además, existe un conjunto de problemas $NP$, donde todos son reducibles en tiempo polinómico entre sí.