El Principio – Máquinas de Turing – Parte I

Bueno, bueno, bueno, bueno, bueno… Sé que estuve desaparecido unos cuantos días, con motivo justificado (justificado para mí); pero estamos volviendo a comenzar a movernos poco a poco con esta web.

Sacando telarañas de apuntes viejos, me encuentro con un tema que es sencillo, pero cuyas implicancias en el mundo de la informática se siguen aplicando hasta el día de hoy.

Hablemos un poco entonces, de las Máquinas de Turing. 

Como es habitual, utilizaremos dichas máquinas como modelo de ejecución de los algoritmos, para el estudio de la computabilidad y de la complejidad computacional temporal. Las máquinas de Turing se presentaron por primera vez en 1936 en una publicación de A. Turing. Desde entonces, la conjetura conocida como Tesis de Church-Turing, de que todo lo computable puede ser llevado a cabo por una máquina de Turing, no ha sido refutada.

Una máquina de Turing es un artefacto que resuelve problemas (computacionales), en su visión más general produciendo o calculando una solución. Por ejemplo, dado el problema de encontrar un camino del vértice v1 al vértice v2 en un grafo, una máquina de Turing que lo resuelve produce, a partir de una instancia, en este caso un grafo G, un camino en G del vértice v1 al vértice v2, si es que existe.

Una segunda visión de máquina de Turing más restringida, que utilizaremos la mayoría de las veces para simplificar las exposiciones sin perder en esencia generalidad, como comprobaremos más adelante, es la de una máquina que sólo puede resolver un problema de decisión, produciendo únicamente la respuesta sí o no ante una instancia.

Volviendo al problema ejemplo, con esta visión una máquina que lo resuelve acepta los grafos que tienen un camino del vértice v1 al vértice v2, y rechaza al resto. Esta es la visión de máquina de Turing reconocedora. Se denomina así porque la resolución de un
problema consiste en reconocer el lenguaje que representa el problema, más precisamente, el lenguaje de las cadenas de símbolos que representan las instancias positivas del problema (en el ejemplo, las cadenas que representan grafos con un camino del vértice v1 al vértice v2).

Hay todavía una tercera visión de máquina de Turing, según la cual se resuelve un problema generando todas sus instancias positivas (en el caso del problema del camino en un grafo, generando todos los grafos con un camino del vértice v1 al vértice v2).
Demostraremos después la equivalencia entre las máquinas generadoras y reconocedoras.

Vamos a trabajar con las tres visiones de máquina de Turing, calculadora, reconocedora y generadora. Ya dijimos que en la gran mayoría de los casos consideraremos la máquina reconocedora. Más aún, salvo mención en contrario, los problemas deberán  entenderse como problemas de decisión, y así los términos problema y lenguaje se tratarán de manera indistinta. Al final de la segunda parte del libro se verán con cierta profundidad los problemas más generales, conocidos como problemas de búsqueda.
A continuación introducimos formalmente las máquinas de Turing, y presentamos algunos ejemplos. Luego definimos distintos modelos de máquinas de Turing y probamos que son equivalentes.

La figura siguiente muestra los componentes de una máquina de Turing:

Los estados pertenecen a un conjunto Q, y los símbolos a un alfabeto Γ. Al comienzo, en la configuración o instancia inicial de M, la cinta tiene la cadena de entrada (o simplemente la entrada), limitada a izquierda y derecha por infinitos símbolos blancos, que se denotan con B. La unidad de control almacena el estado inicial, denotado en general con q0. Y el cabezal apunta al primer símbolo de la entrada, que es su símbolo  de más a la izquierda. Si la entrada es la cadena vacía, denotada con λ, entonces el cabezal apunta a algún blanco.

A partir de la configuración inicial, M se comporta de acuerdo a lo especificado en su función de transición δ. M en cada paso lee un estado y un símbolo, eventualmente los modifica, y se mueve un lugar a la derecha o a la izquierda o no se mueve. Cuando δ no está definida para el estado corriente y el símbolo corriente, M se detiene. Si esto nunca sucede, es decir si M no se detiene, se dice que M tiene o entra en un loop (bucle).

Formalmente, una máquina de Turing M es una 6-tupla (Q, Ʃ, Γ, δ, q0, F), tal que:

• Q es el conjunto de estados de M.
• Ʃ es el alfabeto de las entradas de M.
• Γ es el alfabeto de las cadenas de la cinta de M. Por convención, B ∈ (Γ– Ʃ).
• δ es la función de transición de M. Se define δ: Q x Γ → Q x Γ x {L, R, S}, tal que L representa el movimiento del cabezal a la izquierda, R el movimiento a la derecha, y S indica que el cabezal no se mueve.
• q0 es el estado inicial de M.
• F es el conjunto de estados finales de M (su significado se aclara a continuación).

Considerando la visión de MT reconocedora de un lenguaje, si a partir de la entrada w la MT M se detiene en un estado q ∈ F, se dice que M acepta w. En cambio, cuando a partir de w la MT M se detiene en un estado q ∈ (Q – F) o no se detiene, se dice que M
no acepta (o rechaza) w. El conjunto de las cadenas aceptadas por la MT M es el lenguaje aceptado o reconocido por M, y se denota con L(M). Considerando la visión de MT M calculadora, sólo cuando M se detiene en un estado q ∈ F debe tenerse en cuenta el contenido final de la cinta, es decir la cadena de salida (o simplemente la salida).

Los siguientes son dos ejemplos de MT, uno con la visión de máquina reconocedora y el otro con la visión de máquina calculadora. Más adelante consideraremos las MT generadoras. Luego de los ejemplos trabajaremos en general solamente con la visión de MT reconocedora.

 

---

Ejemplo 1 – Máquina de Turing reconocedora

---

 

Sea el lenguaje L = {aⁿbⁿ | n ≥ 1}. Es decir, L tiene infinitas cadenas de la forma ab, aabb, aaabbb, … Se va a construir una MT M que acepta L, o en otras palabras, tal que L(M) = L. En este caso, el lenguaje L representa directamente un problema de
reconocimiento de las cadenas de un lenguaje.

 

Idea general.

Por cada símbolo a que lee, la MT M lo reemplaza por el símbolo α y va a la derecha hasta encontrar el primer símbolo b. Cuando lo detecta, lo reemplaza por el símbolo β y vuelve a la izquierda para repetir el proceso a partir del símbolo a que está inmediatamente a la derecha de la a anterior. Si al final del proceso no quedan símbolos por reemplazar, la MT M se detiene en un estado de F, porque significa que la entrada tiene la forma anbn, con n ≥ 1. En caso contrario, M se detiene en un estado de (Q – F).

 

Construcción de la MT M.

La MT M = (Q, Ʃ, Γ, δ, q0, F) es tal que:

• Q = {qa, qb, qL, qH, qF}. El estado qa es el estado en que M busca una a. El estado qb es el estado en que M busca una b. El estado qL es el estado en que M vuelve a la izquierda para procesar la siguiente a. El estado qH es el estado en que M detecta que no hay más símbolos a. El estado qF es el estado final.
• Ʃ = {a, b}
• Γ = {a, b, α, β, B}
• q0 = qa
• F = {qF}
• La función de transición δ se define de la siguiente manera:
  • δ(qa, a) = (qb, α, R)
  • δ(qb, a) = (qb, a, R)
  • δ(qb, b) = (qL, β, L)
  • δ(qb, β) = (qb, β, R)
  • δ(qL, β) = (qL, β, L)
  • δ(qL, a) = (qL, a, L)
  • δ(qL, α) = (qa, α, R)
  • δ(qa, β) = (qH, β, R)
  • δ(qH, β) = (qH, β, R)
  • δ(qH, B) = (qF, B, S)

 

Prueba de L(M) = L.

1. Si w ∈ L, entonces w tiene la forma anbn, con n ≥ 1. Por cómo está definida la función de transición δ, claramente a partir de w la MT M acepta w, es decir que w ∈ L(M).
2. Si w ∉ L, entonces M rechaza w, es decir que w ∉ L(M). Por ejemplo, si w = λ, M rechaza porque no está definido en δ el par (qa, B). Si w tiene un símbolo distinto de a o de b, M rechaza porque dicho símbolo no está considerado en δ. Si w empieza con b, M rechaza porque no está definido en δ el par (qa, b). Queda como ejercicio completar la prueba.

 

 

---

Ejemplo 2 – Máquina de Turing calculadora

---

 

Se va a construir una MT M que calcula la resta m – n, tal que m y n son dos números naturales representados en notación unaria. Cuando m ≤ n, M devuelve la cadena vacía λ. En la entrada, m y n aparecen separados por el dígito 0.

 

Idea general.

Dado w = 1m01n, con m ≥ 0 y n ≥ 0, la MT M itera de la siguiente manera. En cada paso elimina el primer 1 del minuendo, y correspondientemente reemplaza el primer 1 del sustraendo por un 0. Al final elimina todos los 0 (caso m > n), o bien elimina todos los dígitos (caso m ≤ n).

 

Construcción de la MT M.

La MT M = (Q, Ʃ, Γ, δ, q0, F) es tal que:

• Q = {q0, q1, q2, q3, q4, q5, q6}. El estado q0 es el estado de inicio de una iteración. El estado q1 es el estado en que M busca el primer 0 yendo a la derecha. El estado q2 es el estado en que M encuentra el primer 0 yendo a la derecha. El estado q3 es el estado en que M encuentra un 1 después de un 0 yendo a la derecha. El estado q4 es el estado en que M yendo a la derecha buscando un 1 después de un 0 encuentra en cambio un blanco. El estado q5 es el estado en queM, iniciando una iteración, no encuentra como primer dígito un 1. El estado q6 es el estado final.
• Ʃ = {1, 0}
• Γ = {1, 0, B}
• F = {q6}
• La función de transición δ se define de la siguiente manera:
  • δ(q0, 1) = (q1, B, R)
  • δ(q1, 1) = (q1, 1, R)
  • δ(q1, 0) = (q2, 0, R)
  • δ(q2, 1) = (q3, 0, L)
  • δ(q2, 0) = (q2, 0, R)
  • δ(q3, 0) = (q3, 0, L)
  • δ(q3, 1) = (q3, 1, L)
  • δ(q3, B) = (q0, B, R)
  • δ(q2, B) = (q4, B, L)
  • δ(q4, 0) = (q4, B, L)
  • δ(q4, 1) = (q4, 1, L)
  • δ(q4, B) = (q6, 1, S)
  • δ(q0, 0) = (q5, B, R)
  • δ(q5, 0) = (q5, B, R)
  • δ(q5, 1) = (q5, B, R)
  • δ(q5, B) = (q6, B, S)

Queda como ejercicio probar que L(M) = L

 

Existen distintos modelos de MT equivalentes al modelo descripto previamente. Dos modelos de MT son equivalentes cuando para toda MT M1 de un modelo existe una MT M2 equivalente del otro, es decir que L(M1) = L(M2). Es útil valerse de distintos modelos de MT, como se irá apreciando en el desarrollo de los temas. Presentamos a continuación algunos ejemplos, y probamos su equivalencia con el modelo inicial. Los ejemplos sirven para la ejercitación en la construcción de MT. El primer modelo de MT que vamos a presentar se adoptará posteriormente como estándar.

 

---

Ejemplo 3 – Máquina de Turing con estados finales q_A y q_R

---

 

Las MT M de este modelo tienen dos estados especiales, el estado qA de aceptación y el estado qR de rechazo. Por definición se los considera fuera del conjunto Q. Cuando M se detiene lo hace sólo en q_A o en q_R.

Formalmente, M se define como la tupla (Q, Ʃ, Γ, δ, q₀, q_A, q_R), tal que la función de transición es

δ: Q x Γ → (Q ∪ {qA, qR}) x Γ x {L, R, S}

M acepta una entrada w cuando a partir de w se detiene en el estado q_A .Si en cambio se detiene en el estado q_R o no se detiene, M rechaza w. Por ejemplo, considerando el mismo lenguaje del Ejemplo 1.1, es decir L = {aⁿbⁿ | n ≥ 1}, se cumple que la siguiente MT M = (Q, Ʃ, Γ, δ, q₀, q_A, q_R) reconoce L.

El conjunto de estados Q ahora es {q_a, q_b, q_L, q_H}, no incluye el estado final qF. Por su parte, la función de transición δ, presentada en forma tabular, es

Que el elemento de la tabla correspondiente al estado q_a y al símbolo a, por ejemplo, contenga la terna q_b, α, R, significa que δ(qa, a) = (q_b, α, R). Los elementos vacíos de la tabla deben entenderse como ternas con el estado de rechazo q_R.

Se cumple que el modelo inicial de MT, con un conjunto de estados finales F, y el modelo de MT con estados q_A y q_R, son equivalentes. Primero veamos que para toda MT M₁ del modelo inicial existe una MT M₂ equivalente del nuevo modelo.

 

Idea general.

La función δ₂ de M₂ es igual a la función δ₁ de M₁, salvo que si δ₁(q, x) no está definida se agregan las transiciones δ₂(q, x) = (q_A, x, S) o δ₂ (q, x) = (q_R, x, S), según q pertenezca o no al conjunto de estados finales F de M₁, respectivamente.

 

Construcción de la MT M2.

Sea M₁ = (Q, Ʃ, Γ, δ₁, q₀, F). Se hace M₂ = (Q, Ʃ, Γ, δ₂, q₀, q_A, q_R), tal que ∀q ∈ Q, y ∀x ∈ Γ:

1. Si δ₁(q, x) no está definida y q ∈ F, entonces δ₂(q, x) = (q_A, x, S)
2. Si δ₁(q, x) no está definida y q ∉ F, entonces δ₂(q, x) = (q_R, x, S)
3. Si δ₁(q, x) está definida, entonces δ₂(q, x) = δ₁(q, x)

 

Prueba de L(M₁) = L(M₂).

1. Sea w ∈ L(M₁). Entonces M₁ a partir de w se detiene en un estado q ∈ F y un símbolo x tal que δ₁ no está definida en (q, x). Entonces por las definiciones anteriores 1 y 3, M₂ a partir de w se detiene en el estado q_A, es decir que w ∈ L(M₂).
2. Sea w ∉ L(M₁). Entonces M₁ a partir de w se detiene en un estado q ∉ F y un símbolo x tal que δ₁ no está definida en (q, x), o no se detiene. Entonces por las definiciones 2 y 3, M₂ a partir de w se detiene en el estado q_R, o no se detiene, respectivamente, es decir que w ∉ L(M₂).

Veamos ahora que para toda MT M₁ del modelo con estados q_A y q_R existe una MT M₂ equivalente del modelo inicial.

 

Idea general.

La función de transición de M₂ es la misma que la de M₁. Lo único que cambia es que al conjunto de estados de M₂ se le agregan q_{A y} q_R, siendo q_A el único estado final de F.

 

Construcción de la MT M₂.

Sea M₁ = (Q₁, Ʃ, Γ, δ, q₀, q_A, q_R). Se hace M₂ = (Q₂, Ʃ, Γ, δ, q₀, F), tal que Q₂ = Q₁ ∪ {q_A, q_R} y F = {q_A}.

 

Prueba de L(M₁) = L(M₂).

Sea w ∈ L(M₁). Entonces M₁ a partir de w se detiene en su estado q_A. Entonces M₂ a partir de w se detiene en su estado q_A, perteneciente a F. Entonces w ∈ L(M₂).

Sea w ∉ L(M₁). Entonces M₁ a partir de w se detiene en su estado q_R o no se detiene. Entonces M₂ a partir de w se detiene en su estado q_R, que no pertenece a F, o no se detiene, respectivamente. Entonces w ∉ L(M₂)

 

 

---

---

---

Ya tenemos mucho para pensar y tratar de entender, seguimos más adelante.