Lenguajes recursivos (LRC) y recursivamente enumerables (LRE)
Un lenguaje $L$ es recursivamente enumerable (LRE) si existe una máquina de Turing que acepta cualquier cadena del lenguaje y se para:
$$ q_0 w \vdash^* x_1 q_f x_2 $$Si $w$ es una palabra del lenguaje ($w \in L$) y $q_f$ es un estado final ($q_f \in F$).
Sin embargo, si $w$ no es del lenguaje ($w \notin L$), la máquina se parará en un estado no final o entrará en un bucle infinito.
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$
Si cualquier cadena $w$ de $L$ y con menos símbolos que $n$ ($|w| \le n$) es aceptada en $O(T(n))$ movimientos, entonces se dice que la MT acepta $L$ en tiempo $T(n)$.
Por tanto, si una computación tiene una complejidad temporal $T(n)$, significa que puede ser resuelta en no más de $T(n)$ movimientos de una MT para un tamaño de problema $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)$
Partiendo de expresiones en forma normal conjuntiva: $e = t_i \lor \ldots \lor t_k $, donde $t_i = s_m \land \ldots \land s_q$ y con $s_i$ variables o sus negaciones.
Dada una expresión $e$, ¿hay alguna asignación de valores a sus variables que haga $e$ verdadera?
Algunos ejemplos:
- $e_1 = (\neg x_1 \lor x_2) \land (x_1 \lor x_3)$
- $e_2 = (x_1 \lor x_2) \land \neg x_1 \land \neg x_2$
Entonces, la complejidad:
- MT estándar: $O(2^n)$
- MT no determinista: $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)$.
$P$ es el conjunto de lenguajes aceptados por una MT determinista en tiempo polinómico.
$$ P = \bigcup_{i \ge 1} \operatorname{TD}(n^i) $$$NP$ es el conjunto de lenguajes aceptados por una MT no determinista en tiempo polinómico.
$$ NP = \bigcup_{i \ge 1} \operatorname{TND}(n^i) $$Sabemos que $P \subseteq NP$, pero…
$$ P \overset{?}{=} NP $$Este es un problema del milenio, todavía sin resolver.
Un lenguaje $L_1$ es reducible en tiempo polinómico a otro lenguaje $L_2$ si existe una MT determinista tal que cualquier cadena $w_1 \in \Sigma_1^+$ puede ser transformada en tiempo polinómico en otra cadena $w_2 \in \Sigma_2^+$ de forma que:
$$ w_1 \in L_1 \iff w_2 \in L_2$$- 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í.