Alan Mathison Turing (1912-1954), matemático británico y pionero  en la teoría del ordenador o computadora. Nació en Londres y estudió en las universidades de Cambridge y Princeton. En 1936, mientras era todavía un estudiante, publicó un ensayo titulado On Computable Numbers (Sobre números calculables), con el que contribuyó a la lógica matemática al introducir el concepto teórico de un dispositivo de cálculo que hoy se conoce como la máquina de Turing. El concepto de esta máquina, que podría efectuar teóricamente cualquier cálculo matemático, fue importante en el desarrollo de las computadoras digitales. Turing también amplió su trabajo matemático al estudio de la inteligencia artificial y las formas biológicas. Propuso un método llamado el test de Turing para determinar si las máquinas podrían tener la capacidad de pensar. Durante la II Guerra Mundial trabajó como criptógrafo para el Foreign Office británico. Murió al administrarse un veneno, quizá por accidente, a la edad de 41 años.

Temas

Maquina de Turing

Construcción de la Máquina de Turing

Modificaciones de la Máquina de Turing

Lenugajes Recursivos y Recursivamente Enumerables

 

Máquina de Turing.

 

  La maquina de Turing es un dispositivo para reconocimiento de lenguajes. Las máquinas de Turing  son más generales que cualquier autómata finito y cualquier autómata de pila, debido a que ellas pueden reconocer tanto los lenguajes regulares como los lenguajes independientes del contexto y, además, muchos otros tipos de lenguajes. Aunque sean más potentes que los dos tipos de autómatas anteriores, todos ellos son bastante similares con respecto a los componentes y las acciones que realizan.

  La organización introducida por la máquina de Turing es bastante sencilla. Consiste en una colección de celdas de almacenamiento que se extiende infinitamente en ambas direcciones (esencialmente es una cinta infinita). Cada celda es capaz de almacenar un único símbolo. La colección no tiene una celda primera ni última y, por lo tanto, tiene una capacidad de almacenamiento ilimitada. A los contenidos de las celdas se les puede acceder en cualquier orden. Además, tendrá, asociada con la cinta, una cabeza de lectura/escritura que puede moverse sobre la cinta y por cada movimiento leerá o escribirá un símbolo.

 

Definición.

Una máquina de Turing es una séptupla  M = (Q, Σ, Γ,  s, Ѣ, F, δ ), donde

 

      Q = Conjunto finito de estados.

      Σ = El alfabeto de entrada.

      Γ = El alfabeto llamado alfabeto de la cinta.

      s ∈ Q es el estado inicial.

      Ѣ ∈ Γ es el símbolo blanco (no está en Σ).

      F ⊆ Q  es el conjunto de estados finales o aceptores.

      δ: Q X Γ —> Q X Γ X {L, R} es una función parcial que se llama función de transición. 

 

  En esta definición se supone que todas las celdas de la cinta es el símbolo Ѣ. La definición requiere que Ѣ no pertenezca a Σ. La función de transición δ transforma pares (q, σ) formados por el estado actual y los símbolos de la cinta en ternas de la forma (p, t, X), donde p es el estado siguiente, t es el símbolo escrito en la cinta y X es el movimiento de lectura/escritura de la cabeza, que puede ser L o R, según que el movimiento sea hacia la izquierda o hacia la derecha (nos imaginamos que la cinta se extiende de izquierda a derecha).

 

  Por ejemplo, la transición δ (q₁, a) = (q₅, Ѣ, R) provoca que la máquina de Turing pase de la configuración

A

B

B

                              ↑
                                             Posición                Estado interno q1
                                            actual de la
                                            cabeza lec/esc.

 

a la configuración

B

B

B

                            ↑

                                Posición                            Estado interno q5
                                                                actual de la
                                                                cabeza lec/esc.

  Observe que las transiciones dependen únicamente del estado actual y del contenido de la celda sobre la que se encuentre la cabeza de lectura/escritura. Por lo tanto, cualquier cadena de entrada se debe presentar a la máquina sobre su cinta. Esto debido a que se requiere que å Í  Γ – { Ѣ } ( y que Ѣ no es un símbolo de entrada).

Consideremos la máquina de Turing definida mediante

Q = {q₁, q₂}

å=(a, b)

Γ=(a, b, Ѣ)

F= {q₂ }

s = q₁

        y  δ dado por:

                                       δ (q₁, a) = (q₁, a, R)

                                       δ (q₁, b) = (q₁, a, R)

                                       δ (q₁, Ѣ ) = (q₂, Ѣ, L)

    Esta máquina empieza sus operaciones en el estado q₁. Si el contenido de la celda de la cinta sobre la que se encuentra la cabeza de lectura/escritura es a, la transición que se puede aplicar es δ (q₁, a) =  (q₁, a, R). La máquina de Turing sobrescribirá la a que está en la cinta con otra a (es decir no se producirá ninguna cambio en el contenido de la cinta), se moverá una celda hacia la derecha y permanecerá en el estado q₁.

    Cualquiera de la a´s que haya en la cinta ya sea en la nueva posición como en cualquier otra que esté a la derecha, no se cambiará, sin embargo las b´s serán sustituidas por a´s (por medio de la transición δ (q₁, b) = (q₁, a, R) ). Si la máquina de Turing encuentra un blanco (el símbolo Ѣ), se moverá una celda hacia la izquierda y pasará al estado final q₂.

    No hay ninguna transición desde el estado q₂, con lo que la máquina de Turing parará una vez que llegue a ese estado.

    Estos gráficos representan las distintas etapas del proceso para la máquina de Turing dada, que empieza con una configuración inicial muy sencilla:

          ↑ Estado q1                                             ↑ Estado q1                                          ↑ Estado q1

                          ↑ Estado q1                     Estado q1 ↑                  Estado q2 ↑

    Representar las configuraciones de una máquina de Turing de esta forma es bastante pesado.     Cualquier configuración viene determinada por el estado actual, el contenido de la cinta y la posición de la cabeza de lectura/escritura sobre la cinta. A continuación veremos las dos notaciones que más se emplean para representar esta información de una manera más conveniente. La primera representa una configuración como un par (qi, w₁ σ w₂), donde qi   es el estado actual, w₁ es la cadena de la cinta que precede a la celda sobre la que se encuentra la cabeza de entrada/salida, σ  es el símbolo de la cinta sobre el que se encuentra la cabeza de entrada/salida y w₂, es la cadena que hay a continuación de la cabeza de entrada/salida. Por tanto, en el ejemplo anterior la configuración inicial de nuestra máquina de Turing podría ser (q₁, Ѣabba), la segunda sería (q₁, abba) y así  sucesivamente.  Otra  notación  alternativa  viene  dada por una cadena a₁a₂ ... a_k - 1 q_i a_k ... a_n, que representa a la configuración (qi, wa_ku); es decir, la cabeza de entrada/salida se coloca sobre la celda que contiene a_k y el estado actual es q_i.            Obsérvese que la cadena  a₁a₂ ... a_k - 1 q_i a_k ... a_n indica que la cabeza de entrada/salida se encuentra sobre el símbolo de la cinta que aparece siguiendo al estado. Por lo tanto, la primera de las dos configuraciones del ejemplo anterior se puede representar como q₁abba y aq₁bba.              

    Usaremos estas dos notaciones indistintamente. Las configuraciones de una máquina de Turing se conoce como descripciones instantáneas (DIS).

    Sea cual sea la notación que utilicemos, denotaremos el paso de una configuración a otra por medio del símbolo ya familiar ⊢. Por lo tanto, en el ejemplo anterior se tiene que

     (q₁, abba) ⊢ (q₁, abba) ⊢ (q₁, aaba) ⊢ (q₁, aaaa) ⊢ (q₁, aaaaѢ) ⊢ (q₂, aaaa)

o

        q₁abba ⊢ aq₁bba ⊢ aa q₁ba ⊢ aaaq₁a ⊢ aaaa q₁Ѣ ⊢ aaa q₂a

Construcción de la Máquina de Turing

    Las máquinas de Turing pueden desempeñar muchas actividades además del reconocimiento de lenguajes. De hecho, las máquinas de Turing se toman como modelos teóricos de las computadoras.  Por ahora nos centraremos en la forma de simplificar la construcción de una máquina de Turing.  La idea básica  para simplificar la construcción de una máquina de Turing es construir una colección de máquinas de Turing sencillas y combinarlas de diferentes formas con el fin de crear una más compleja.

    Podemos combinar dos máquinas de Turing permitiendo que compartan la misma cinta y, que cuando una termine su ejecución, la otra empiece. El contenido de la cinta cuando comienza la ejecución de la segunda máquina de Turing, está formado por todo lo que dejó la primera máquina de Turing, y la cabeza de lectura / escritura de la segunda se situará, al comienzo de la ejecución, sobre la celda de la cinta sobre la que terminó la primera.

Ejemplo.

 Sea M₁  dada por

                               Q₁ = { q₁, q₂, q₃, q₄}  

                                  å = {a}

                                Γ = {a, b}

                                S₁ = q₁

                                      F₁ = {q₄}

  Con δ₁ de la forma siguiente

                               δ₁(q₁, a) = (q₂, a, R)

                               δ₁(q₁, b) = (q₂, b, R)

                               δ₁(q₂, a) = (q₂, a, R)

                                       δ₁(q₂, b) = (q₃, b, L)

                               δ₁(q₃, b) = (q₄, b, R)

                               δ₁(q₃, a) = (q₄, a, R)

  Sea M₂ dada por

                               Q₂ = {p₁, p₂}

                             å y Γ los mismos de M₁

                                       s₂ = p₁

                               F₂= {p₂}

  Con δ₂ como se escribe a continuación

                               δ₂(p₁, a) = (p₂, a, R)

                                       δ₂(p₁, b) = (p₂, a, R)

    Obsérvese que M₁ busca el primer blanco que haya a la derecha de donde ha comenzado, mientras que M₂ escribe una a y para. (La a se escribe independientemente del contenido de la celda actual).  Al combinar estas dos máquinas de Turing de forma que una computación de M₁ vaya seguida por una de M₂, obtenemos un dispositivo que primero busca hacia la derecha el primer b y después escribe una a en todas las celdas. Representaremos La combinación de estas dos máquinas de Turing mediante M₁M₂ para indicar que la computación de M₁ va seguida por la computación de M₂.

Definición.

    Sean M₁ y M₂ dos máquinas de Turing sobre el mismo alfabeto de entrada å y el mismo alfabeto de la cinta Γ, donde:

                                                M₁ = (Q₁, å, Γ, s₁, Ѣ, F₁, δ₁)

y

                                                M₂ = (Q₂, å, Γ, s₂, Ѣ, F₂, δ₂)

    Se supone que Q₁  Ç  Q₂ = Æ . La composición de las máquinas de Turing M₁ y  M₂ es la máquina de Turing M = (Q,  å,  Γ,  s, b, F, δ ) que se denota M₁M₂, donde:

Q = Q₁ ⋃ Q₂

s = s₁

F = F₂

    Nos vamos a referir a la máquina de Turing M₁ del ejemplo anterior como R_Ѣ.  Es decir, R_Ѣ busca el primer blanco que haya a la derecha de la posición actual de la cabeza.  Consideremos una cinta

                                             ↑ Posición
                                                            actual de la
                                                            cabeza
 

  La máquina de Turing compuesta R_ѢR_Ѣ terminaría en la posición:

                                                                                   ↑ Posición
                                                                                                            de la
                                                                                                            cabeza

mientras que la máquina de Turing compuesta R_ѢR_ѢR_Ѣ  terminará en la posición

                                                                                          ↑ Posición
                                                                                                                     de la
                                                                                                                     cabeza

    Otra forma de especificar las transiciones es el uso de una tabla. La tabla de las transiciones correspondientes a R_Ѣ sería:                    

Obsérvese que una de las columnas se especifica para un símbolo de la cinta en particular y la otra especifica el resto de símbolos de la cinta. La transición δ (q₂, σ) = (q_2, σ,R) de la columna etiquetada con  σ ¹ Ѣ indica que para todo símbolo de la cinta σ que sea distinto de Ѣ, la máquina de Turing escribe σ en la cinta, se mueve a la derecha y permanece en el estado q₂.  Aunque al principio habíamos especificado RѢ sólo para el alfabeto de la cinta Γ = {a,Ѣ}, ahora hemos especificado RѢ para todo alfabeto de cinta que incluya Ѣ como el blanco.

Modificaciones de las Máquinas de Turing

    Hay otras definiciones de las máquinas de Turing que son equivalentes a la nuestra. Algunos de esos modelos alternativos son mucho más complicados aunque todos tienen la misma potencia computacional (o de cálculo).

    Muchas de ellas denotan mayor flexibilidad al diseño de una máquina de Turing que resuelva un problema en particular.  Vamos a ver primero unas pequeñas variaciones de nuestra definición original.

    Recuérdese que la máquina de Turing sencilla L_Ѣ sitúa la cabeza de lectura/escritura sobre el primer Ѣ que haya a la izquierda de la posición actual. Para hacerlo, buscamos fuera de la celda actual y retrocedemos esto es debido a que se requiere que por cada transición se mueva la cabeza de la cinta.

La función de transición estaba definida como:

δ :Q x Γ →   Q x Γ x  {L, R}

y puede ser modificada domo

δ: Q x Γ →   Q x Γ x  {L, R, S}

donde S significa “permanecer”, es decir, no mover la cabeza de lectura/escritura. Por lo tanto δ(q, σ ) = (p, σ’, S) significa que se pasa del estado q al p, se escribe σ’ en la celda actual y la cabeza se queda sobre la celda actual.  Obsérvese que en esta definición está contenida la nuestra, puesto que ésta es una extensión de la máquina de Turing que hemos definido.

    Por otro lado, una máquina de Turing para la cual esté definida δ(q, σ ) = (p, σ’, S), se puede simular por medio de una máquina que corresponda a nuestra definición original, añadiéndole simplemente los estados y movimientos de la forma δ(q, σ ) = (p’, σ’, R) y δ(p’,τ ) = (p, τ, L) y/o de la forma δ(q, σ ) = (p’, σ’, L) y δ(p’,τ ) = (p, τ, R) para todo τ ∈ Γ.

    Otra modificación sencilla de nuestra máquina de Turing  básica es aquella mediante la cual cada celda de la cinta se divide en subceldas. Cada subcelda es capaz de contener un símbolo de la cinta. La cinta

tiene cada celda subdividida en tres subceldas. Se dice que esta cinta tiene múltiples pistas. Puesto que cada celda de esta máquina de Turing contiene múltiples caracteres, el contenido de las celdas de la cinta puede ser representado mediante n-uplas ordenadas. En ejemplo anterior, las celdas de la cinta contienen (Ѣ, a , a), (b ,a,a) (b,b, Ѣ). Por lo tanto, los movimientos que realice esta máquina dependerán de su estado actual y de la n-tupla que represente el contenido de la celda actual.

    La máquina de Turing multipista no tiene más potencia que la máquina original. Sin embargo, hace que sea más fácil la construcción de máquinas de Turing que resuelvan ciertos problemas.

    Otra modificación sencilla (y bastante común) que puede realizarse en nuestra definición de máquina de Turing es que se use una cinta que se extienda infinitamente en una única dirección.

Generalmente, se tiene una cinta que se extiende infinitamente hacia la derecha. No está permitido realizar ningún movimiento hacia la izquierda a partir de la celda del extremo izquierdo. Desde luego, cualquier máquina de Turing de esta forma, puede ser simulada por una de las que responden a nuestra definición original.  Para cada computación, simplemente marcaremos una de las celdas de nuestra cinta infinita por los dos lados, como la celda que se encuentra en el límite izquierdo.

    Una modificación de nuestra definición, que es mas complicada, es la máquina de Turing multicinta. Esta máquina de Turing tiene varias cintas, cada una de las cuales tiene su propia cabeza de lectura/escritura. Las cabezas de lectura/escritura se controlan independientemente (es decir, al mismo tiempo, no tienen que moverse en la misma dirección, ni realizar el mismo número de movimientos, ni incluso, hacer nada a la vez). En un solo movimiento esta máquina de Turing

1.      Cambia de estado dependiendo del estado actual y del contenido de las celdas de todas las cintas, que están analizando actualmente las cabezas de lectura/escritura.

2.      Escribe un nuevo símbolo en cada una de las celdas barridas por sus cabezas de lectura/escritura.

3.      Mueve cada una de sus cabezas hacia la izquierda o hacia la derecha (de forma independiente al resto de las cabezas).

  Por tanto la función de transición para una máquina de Turing con n cintas, es de la forma:

            δ: Q x Γⁿ →   Q x Γⁿ x  {L, R,}ⁿ

    Aunque una máquina de Turing multicinta parece bastante distinta y posiblemente más potente que nuestra máquina de Turing definida originalmente, las dos son equivalentes en el sentido de que cada una de ellas puede ser simulada por la otra.

    Otra modificación que se puede hacer en nuestra máquina de Turing original consiste en permitir que la cinta tenga muchas dimensiones. Por ejemplo, una cinta de dos dimensiones que se extienda hacia abajo y hacia arriba, al igual que hacia la derecha y hacia la izquierda. Dependiendo del estado actual de la máquina de Turing y del símbolo analizado, cambia de estado, escribe un símbolo en la celda actual y se mueve a la izquierda, a la derecha, hacia arriba o hacia abajo. Por tanto, la función de transición para esta máquina de Turing  queda de la siguiente forma:

                                  δ : Q x Γ →   Q x Γ x  {L, R, U, D}

    Una máquina de Turing multidimensional simula, fácilmente, a una máquina de Turing estándar. Simplemente realiza todas sus computaciones en una única dimensión. Una máquina de Turing estándar también puede simular una máquina de Turing multidimensional y, por lo tanto, la complejidad y flexibilidad adicional que se debe a su múltiple dimensión, no es una capacidad real. 

    Finalmente, una modificación importante que se puede introducir en la definición original es la eliminación del requerimiento de que la regla de transición  sea una función. Esta máquina de Turing se llamará máquina de Turing no determinista, ya que para un estado actual y el símbolo actual de la cinta, puede haber un número finito de movimientos a elegir. Por lo tanto, la regla de transición, ∆ de dicha máquina, satisface

                                                 ∆(q, σ) Í  Q x Γ x  {L, R}

Por ejemplo, si la máquina de Turing tiene una transición

                                   ∆(q₁, σ) = {( q₁, b, R ), (q₂, a, L) }     

entonces los movimientos

                     (q₁, abbab) ⊢ (q₁, abbbb)   y   (q₁, abbab) ⊢ (q₂, abbab)   

son posibles.                                                  

    Ya que cualquier máquina de Turing determinista es también no determinista, es lógico que una máquina de Turing determinista se puede simular mediante una no determinista. También una máquina de Turing determinista puede simular una no determinista. Por tanto, no se gana ninguna potencia adicional a causa del no determinismo.

    En esta sección hemos descrito varias modificaciones a realizar sobre la máquina de Turing original, ninguna de las cuales tiene mayor o menor potencia que la original. Entonces cabe preguntarse porque nos hemos molestado en estudiarlas si ninguna de ellas aporta ninguna ganancia en cuanto a capacidad computacional, o por que no nos hemos centrado en la mas sencilla de todas ellas.  Una de las razones es que, a partir de ahora, conocemos formas distintas de resolver problemas mediante la máquina de Turing. Si una de ellas resolviera un problema de forma más fácil que la original entonces, sin temor a perder generalidad, usaremos dicha variante.

    Otra razón aún más profunda para el estudio de estas modificaciones y sus equivalencias con el original, es que con esto se comprende aún más la actualidad de las máquinas de Turing. 

Lenguajes Recursivos y Recursivamente Enumerables

    Recordaremos que una cadena w sobre algún alfabeto es aceptada por una máquina de Turing M, cuando una computación que empezó con w en la cinta de M y con M en su estado inicial, termina con M en un estado final. Por otro lado, w  se puede rechazar de dos formas, ya sea porque M para en algún estado que no es de aceptación o porque M nunca para. Los dos métodos de rechazo de cadenas no son equivalentes. Por tanto, hemos definido los lenguajes recursivamente enumerables como los lenguajes que son aceptados por una máquina de Turing (de alguna forma) y los lenguajes recursivos como los lenguajes aceptados por alguna máquina de Turing que siempre para sobre alguna entrada.  Formalmente, daremos la siguiente definición

Definición:

    Un lenguaje L sobre un alfabeto å se dice que es recursivamente enumerable si es aceptado por alguna máquina de Turing. Es decir, L es recursivamente enumerable si para alguna máquina de Turing M tenemos que:

L = (w ∈ å* | qw ⊢*   upv  para p ∈ F y u, v ∈ Γ *)

(donde q es el estado inicial de M y F es el conjunto de estados finales de M).

    Un lenguaje L es recursivo si L es recursivamente enumerable y hay alguna máquina de Turing que para sobre todas las entradas que acepta L.

    De esta definición se deduce que todo lenguaje que es recursivo, también es recursivamente enumerable.

Teoremas

      Si L es un lenguaje regular, entonces L también es un lenguaje recursivo.

      Si L es un lenguaje independiente del contexto, entonces L es un lenguaje recursivo.

      Si L₁ y L₂ son lenguajes recursivos, entonces L₁ Ç  L₂ también lo es.

      Si L es un lenguaje recursivo, entonces å* - L es un lenguaje recursivo.

      (Esta es una propiedad que, en general, no se cumple para los lenguajes recursivamente enumerables).

      Supongamos que å es un alfabeto. Ya que S* es numerable, podemos enumerarlo como S* = {w1,w2,w3,...}.  Por lo tanto  se puede listar todas las máquinas de Turing  sobre S como M1, M2,... Sea

                                 L = {w_i ,| w_i  es aceptado por M _i }

Este lenguaje es recursivamente enumerable, pero su complemento no.  Hay un lenguaje recursivamente enumerable L para el cual å* - L no es recursivamente enumerable.

Obsérvese que el lenguaje L descrito aquí no puede ser recursivo porque, si lo fuera, su complemento también lo sería y, por lo tanto, L sería recursivamente enumerable. Luego tendremos un lenguaje recursivamente enumerable que no es recursivo. Por consiguiente, la inversa de la sentencia que dice que todo lenguaje recursivo también es recursivamente enumerable no es cierta.

      Si L₁ y L₂ son lenguajes recursivamente enumerables, entonces L₁ È L₂ también es recursivamente enumerable.

      Si L es un lenguaje recursivamente enumerable para el cual  å* - L también es recursivamente enumerable, entonces L es un lenguaje recursivo.

      Un lenguaje L es recursivamente enumerable si y sólo si L es enumerado por alguna máquina de Turing.

Por tanto, la capacidad de ser enumerado por una máquina de Turing, caracteriza completamente a los lenguajes recursivamente enumerables.