Clases de Complejidad, parte II

Por mucho mucho tiempo se han resuelto tareas de cómputo de muchas maneras y mediante muchos dispositivos desde un abaco hasta la moderna computadora, la pregunta es: ¿Que modelo matemático captura todas las maneras de hacer cómputo? La respuesta es: La máquina de Turing ¹ la cual es un modelo simple pero suficiente para estudiar muchos aspectos de la computación como su eficiencia.

La máquina de Turing es una simple estructura de datos, una cadena de símbolos (cinta); las operaciones permitidas (efectuadas por un "cabezal") son: leer un símbolo de la cadena, moverse hacia la izquierda o derecha y escribir un nuevo símbolo en la posición actual o "expandirse" como explicaremos más adelante, las operaciones a realizar se basan en un conjunto de "reglas". Este modelo es simple pero es capaz de expresar cualquier algoritmo.

Formalmente una máquina de Turing es una tupla M = (Q, Σ,δ, q₀) donde:
Q: es un conjunto finito de estados.
Σ: es un conjunto finito de simbolos, simpre contiene el simbolo en blanco ⌊⌋ y el símbolo de "comienzo" ►.
δ: es una función de transición que mapea Q × Σ → ( Q ∪ {h, "si", "no"}) × Σ × {← (izquierda) ,→ (derecha), - (no moverse)}.
q₀: es el estado inicial q₀ ∈ Q.

Se asume que el estado h es estado de paro (halt), "si" es el estado de aceptación y "no" el estado de rechazo. En pocas palabras δ es una regla que especifica para cada combinación de un estado actual q ∈ Q y un simbolo actual σ ∈ Σ una transición a un estado p, un símbolo ρ se sobreescribe en σ y el cursor se mueve hacia una dirección o se queda en la posición actual, esto es δ(q, σ) → (p, ρ D), donde D = {←, →, - } son las direcciones a las cuales se puede mover el cursor (cabezal que lee los símbolos).

El cabezal siempre realiza una acción hasta que se alcanza algun estado de paro como {h, "si", "no"}) Si es asi se dice que la maquina ha parado (halted). Si el estado "si" se alcanza se dice que la máquina acepta la entrada (la cadena de simbolos), si se alcanza el estado "no" se dice que la máquina rechaza la entrada. Si h se ha alcanzado la salida es la cadena de M al tiempo de paro, la cadena de salida en este caso se denota como y.

Si M acepta o rechaza la entrada x entonces M(x) = "si" o "no" respectivamente. Si se alcanza h, M(x) = y, Si M nunca llega a un estado de paro con la cadena x se escribe M(x) = "↗". En la siguiente figura se muestra en la parte izquiera una máquina de Turing y en la parte derecha se muestra la computación, M simplemente inserta un espacio en blanco entre el símbolo de inicio y la cadena de entrada. Cada operación de la maquina de Turing se define como configuración.



Cuando se va de una configuración a otra se dice que se ha dado un paso en el ejemplo de la figura anterior de la configuración inicial a la final se dieron 15 pasos. Hasta este punto se ha descrito a grandes rasgos que es una máquina de Turing, como "funciona" y unos conceptos básicos, ahora profundizaremos en ciertos conceptos que son muy necesarios para la definición de clases de complejidad.

Máquinas de Turing como algoritmos

Las máquinas de Turing son ideales para resolver cierto tipos de problemas especializados sobre cadenas, como aceptar o decidir "lenguajes". A continuación se listarán una definiciones de utilidad:

Sea L ⊂ (Σ - {⌊⌋})* un lenguaje, es decir, un conjunto de cadenas de simbolos. Sea M una máquina de Turing tal que para cada cadena x ∈ (Σ - {⌊⌋})*. Decimos que M decide L si y solo si x ∈ L, entonces M(x) = "si" y si x ∉ L then M(x) = "no". Si M decide L entonces L es llamado un lenguaje recursivo.

Una máquina Turing acepta un lenguaje L si para toda sucesión x ∈ (Σ - {⌊⌋})* aplica que si x ∈ L, M(x) = “si", pero si x ∉ L, M(x) ="↗". Los lenguajes aceptados por alguna máquina Turing son recursivamente numerables. Nota que si L es recursivo, también es recursivamente numerable.

Las funciones computables son el objeto básico de estudio de la teoría de la computabilidad y consisten en las funciones que pueden ser calculadas por una máquina de Turing. Suponga que ƒ es una función de x ∈ (Σ - {⌊⌋})* a Σ* y sea M una maquina de Turing con alfabeto Σ Desimo que M computa a ƒ si para cualqueir cadena x ∈ (Σ - {⌊⌋})*, M(x) = ƒ(x). Si tal M existe, ƒ es llamada una función recursiva.

Maquinas de Turing con multiples cadenas.

Para definir formalmente el tiempo y el espacio requerido por una máquina de Turing para hacer computaciones, se debe introducir una generalización de esta, la máquina de Turing con multiples cadenas o más bien máquina de Turing con k cadenas, donde k >= 1. La máquina se define como anteriormente se hizo, la función de transición decide el siguiente estado igual que antes, solo que ahora decide para cada cadena el símbolo a escribir y la dirección del cabezal viendo el estado y símbolo actual de cada cadena. La salida de la computación de una máquina de Turing de k-cadenas con entrada x es como en la descirta anteriormente (k=1) con la sola diferencia que la salida se lee del última cadena cuando la máquina se detiene. La configuración y el número de pasos se define análogamente a como se definio anteriormente.

Ahora viene lo más importante, si para una maquina con k cintas se llega de una configuración incial a una configuración de paro en t pasos, entonces el tiempo requerido por M sobre la entrada x es t. Es decir, el tiempo requerido es simplemente el número de pasos para parar. Si M(x) ="↗" entonces el tiempo requerido por M sobre x es infinito.

Sea ƒ una función de N a N. Decimos que la maquina M opera con tiempo ƒ(n) para cualquier entrada x, el tiempo requerido por M sobre x es a lo más ƒ(|x|). Supongamos que un lenguaje L ⊂ (Σ - {⌊⌋}) es decidido por una máquina de Turing multicadena en tiempo ƒ(n). Se dice que L ∈ TIME(ƒ(n)). Esto es TIME(ƒ(n)) es un conjunto de lenguajes que pueden ser decididos por máquina de Turing multicadenas que operan con un tiempo acotado por ƒ(n). TIME(ƒ(n)) es una clase de complejidad de tiempo, pero tambien tenemos clases de complejidad de espacio.

Cuando la máquina de Turing para, el cabezal se detiene en cierta posición de la última cinta, denotemos w como la parte izquierda de la cadena tomando en cuenta el simbolo sobre el cual esta el cabezal y u la parte de la cadena a la derecha del cabezal. Entonces el espacio requerido por M es Σ_i=1^k-1|w_iu_i|. Supongase ahora que ƒ es una funcion de N a N. Entonces decimos que una máquina de Turing M opera en un espacio acotado por ƒ(n). Sea L un lenguaje, decimos que L estan en la clase de complejidad de espacio SPACE(ƒ(n)) si existe una máquina de Turing con entrada y salida que decida L y opere en un espacio acotado por ƒ(n).

Maquinas no deterministas

Una máquina no determinista es una tupla M = (Q, Σ,Δ, q₀) donde Q, &Sigma y σ se definen de igual manera que lo hicimos anteriormente, salta a la vista la diferencia, en una máquina no determinista no tiene una sola acción siguiente definida, si no una opción de acciones, Δ no es una función es una relación &Delta ⊂ (Q × Σ) × [( Q × ∪ {h, "si", "no"}) × Σ × {←, →, -}. Esto es para cada combinacion de estado símbolo hay más de una acción a realizar o ninguna.

Una entrada es aceptada si hay mas de una secuencia de opciones no determinadas que resulten en "si". Otras opciones podrían resultar en rechazo, solo una computación aceptable es suficiente. La cadena es rechazada sí y sólo sí no hay secuencias de opciones puede conducir a aceptar la cadena.

Decimos que una máquina N decide un lenguaje L en tiempo ƒ(n), si N decide L y hay k cantidad de pasos de una configuración incial a una configuracion de paro, entonces k <= ƒ(|x|). Esto es, se requiere que N, ademas de aceptar a L, no tengas rutas de computación mas grandes que ƒ(n). El conjunto de lenguajes decididos por una máquina de Turing no determinista en tiempo ƒ es la clase de complejidad NTIME(ƒ(n)).

---

[1] Turing, A.M. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 2, 42, 230-265. 1936.