Artículo escrito en colaboración con Kiko Llaneras.

El pasado fin de semana se cumplieron 100 años del nacimiento de Alan Turing, considerado, sirva el tópico, uno de los padres de la informática. Cives ya escribió hace unos días sobre Turing referenciando un brillante artículo de Dennet. Lo que pretendemos ahora es dar una perspectiva «más computacional».

Su vida es bien conocida. Fue estudiante y profesor de la Universidad de Cambridge, aunque se doctoró por Princeton. Desde la universidad realizó sus trabajos en los campos de la computación, las matemáticas, y la Inteligencia Artificial. Durante la Segunda Guerra Mundial trabajó en Bletchley Park, la instalación británica encargada de descifrar las comunicaciones alemanas. Allí desarrolló el dispositivo electromecánico (todavía no un computador) que rompió el cifrado de las máquinas Enigma que usaban los alemanes, un acontecimiento que algunos juzgan trascendental en el devenir del guerra. En 1952 se hizo pública su homosexualidad y se inició un proceso judicial contra él, en el que se negó a defenderse ya que “no había hecho nada malo”. Fue hallado culpable de  “indecencia grave y perversión sexual» y tuvo que someterse a una castración química para evitar la pena de cárcel.  Se suicidó dos años después ingiriendo una manzana con cianuro.

Algo llamativo del trabajo de Alan Turing es que sus contribuciones fueron muy variadas, pasando de trabajar en cuestiones de teoría matemática, e incluso de filosofía, a la construcción de cacharros útiles en plena guerra mundial. Es esto último por lo que más se le conoce —por haber pateado nazis—, pero en el mundo de la computación se le recuerda, sobre todo, por una contribución teórica: la máquina que lleva su nombre.

La maquina de Turing

La Máquina de Turing constituye la base de todos los computadores actuales y por eso quizás sea la aportación más valiosa del científico inglés. En realidad la Máquina de Turing fue revolucionaria en dos sentidos: primero, porque fue la primera propuesta de una máquina generalista y flexible cuyas funciones vendrían determinadas por un programa alojado en una memoria abstracta. Y segundo, porque Turing dio una descripción formal y rigurosa de su máquina dentro del marco de la Teoría de Autómatas.

Un autómata puede entenderse como una descripción matemática de una Máquina de Estados Finita. Básicamente, una máquina capaz de «saltar» entre estados siguiendo unas reglas de «transición» y en respuesta a un «estado inicial» y ciertos eventos de «entrada». Estas Máquinas de Estados Finitas sirven para implementar algoritmos, lo que vale tanto para resolver problemas abstractos de computación o lenguaje, como para gobernar de forma automática un cacharro físico del tipo una lavadora, un satélite espacial o un robot que invierta en bolsa. Las máquinas de estados son artilugios útiles y la Teoría de Autómatas es un marco teórico para estudiarlos.

Desde la perspectiva de la Teoría de Autómatas, un autómata es una máquina teórica capaz de aceptar un lenguaje más o menos avanzado. Un lenguaje es un conjunto de palabras definido sobre un alfabeto. Y un alfabeto es un conjunto de símbolos que utilizamos para definir cadenas (palabras).

Formalmente, dado un alfabeto ∑ = {a, b, c} y la palabra vacía ℰ, definiremos como cierre de sigma el conjunto de todas las palabras que se pueden formar con nuestro alfabeto, es decir, ∑* = {ℰ, a, b,c, ab, ac, bc, abc, aa, …}. Un lenguaje A será, pues, un subconjunto de ∑*.

Tomando como base la jerarquía de Chomsky (sí, ese Chomsky), los distintos lenguajes se pueden clasificar según su rigidez o generalidad (más o menos restricciones sobre sus cadenas). Los lenguajes más sencillos son los lenguajes regulares.

Así, un Autómata Finito Determinista es un modelo teórico que se define como una 5-tupla M=(∑, Q, F, s, δ). Donde ∑ el alfabeto de entrada, Q un conjunto finito de estados, F un subconjunto de Q que define los estados finales, s el estado inicial, y δ la función de transición, definida como δ:Q×∑→Q.

Una cadena w se dice aceptada por un autómata finito determinista si δ(s, w) ∈ F. Es decir, si partiendo del estado inicial s, la cadena w genera una secuencia de estados que lleva al autómata a un estado final válido.

Dado un lenguaje regular existe un Autómata Finito que lo acepta, y viceversa.

Volvamos de nuevo a Turing.

El inglés estaba interesado por una cuestión fundamental para la naciente ciencia de la computación: el significado mismo de que una tarea fuese computable. Buscando una respuesta  publicó su artículo “On Computable Numbers” en 1936. En ese trabajo el inglés definía algoritmo y computador y proponía una noción formal de computación que hoy llamamos Turing-computación. Esa noción es la base de la famosa Tesis de Church-Turing:

Todo tarea algorítmicamente (Turing-)computable puede ser computada mediante una Máquina de Turing.

De esta forma Turing nos proveía de un formalismo para la computación.

¿Pero que es una Máquina de Turing? En realidad es una idealización, que como habréis visto en el fantástico doodle de Google, consiste en una cinta infinita de casillas en serie, conteniendo éstas símbolos, que pueden ser leídos por un cabezal lector/escritor capaz de desplazarse sobre la cinta. Esos desplazamientos permiten que una Máquina de Turing sea capaz de computar algoritmos.

Formalmente definiremos una Máquina de Turing como una 7-tupla MT = (Q, ∑, Γ, s, b, F, δ). Donde Q es el conjunto de estados, ∑ el alfabeto de entrada, Γ el alfabeto de la cinta, s el estado inicial, b el símbolo blanco, F el conjunto de estados finales, δ la función de transición definida como δ : Q × Γ → Q × Γ × {L, R}, y donde L y R representan el desplazamiento del cabezal a izquierda y derecha, respectivamente.

Nótese que una de las ventajas de la Máquina de Turing sobre otros modelos teóricos es que permite aceptar un conjunto de lenguajes más generalista: los lenguajes recursivamente enumerables (que contienen a los lenguajes regulares mencionados antes).

Una cadena w se dice aceptada por una Máquina de Turing si al terminar de computarla el cabezal se encuentra parado en un estado final ∈ F.

Así, una función f, entendida como formalización del concepto de algoritmo (f:N→N), será Turing-computable si, dado f(w)=u, existe una Máquina de Turing MT = (Q, ∑, Γ, s, b, F, δ) que verifique sw ⊢* qu, con q∈ F.

El éxito de Turing está en la última afirmación, que supone demostrar que su máquina podía computar cualquier problema representable mediante un algoritmo computable; y de forma especular, que un algoritmo es (Turing-)computable si puede ser computado por una Máquina de Turing.

Pero recordad que la máquina de Turing no es una tecnología práctica de computación —ni lo pretende—, sino que es un dispositivo hipotético, idealizado y simple, que representa la generalidad de (casi) todas las distintas máquinas de computar que podemos concebir y fabricar. Una máquina de Turing es una representación meramente teórica, pero utilísima para estudiar el poder de la computación y lo que quizás sea más importante, para entender también sus límites.

 


21 comentarios

  1. […] "CRITEO-300×250", 300, 250); 1 meneos Turing-computable politikon.es/2012/06/30/turing-computable/  por elhombrepancho hace […]

  2. Cives dice:

    Qué artículo más cojonudo, joder

  3. Ander dice:

    Vamos a ver:
    a) Sospecho que este es un gran post gracias al cual podemos aprender lógica, lingüística, informática, matemáticas, por qué la máquina de Alan Turing es la leche (y lo que es también) y qué coño hace Chomsky aparte de eso otro, algo que yo haría encantado, PERO…
    b) No lo he entendido. Modestamente hablando, creo que no soy una persona muy obtusa y/o inculta, por lo que creo que esto se debe a, digamos, el uso indiscriminado de letras griegas y artefactos follamentes como «Una cadena w se dice aceptada por un autómata finito determinista» ¿Me explico?

    Suspenso en divulgación para un post que, estoy seguro, merece ser comprendido por mucha gente.

    • Cives dice:

      Ander, el post lleno de enlaces y está wikipedia si te haces un lío 🙂 Hay cosas que son muy complicadas de explicar sin un mínimo de notación o de jerga.

    • PaulJBis dice:

      Es que es complicado explicar todo eso en un solo artículo… 🙂

      Un libro que a mí me sirvió de mucha ayuda fue «Gödel, Escher, Bach: un grácil y eterno bucle», de Douglas Hofstadter. Es sobre el teorema de Gödel, pero también hay una explicación sobre la tesis Church-Turing. Toda la primera parte del libro consiste en una especie de tutorial de lógica formal, y al final de dicha parte te explica el teorema de Gödel, de forma que entiendes por fin por qué es relevante.

      Debo decir que lo leí hace mucho tiempo, así que no sería capaz de hacer un resumen aquí de todo lo que explica (aparte de que son más de 800 páginas), pero sí recuerdo que cuando lo leí, lo entendí… 🙂

  4. PaulJBis dice:

    Vale, me habéis inspirado para releer «Gödel Escher Bach» y dar un par de vueltas por la Wikipedia (en un sábado por la noche, nada menos), y *creo* que lo entiendo más o menos. En parte, escribo esto aquí también para comprobar si voy bien o estoy completamente despistado, así que agradecería correcciones.

    Vamos a ver: imagínate que quieres averiguar si un número dado es la suma de 2 números primos (conjetura de Goldbach y tal). Eso lleva un número finito de pasos: si, por ejemplo, el número es el 1727, no tienes más que ir sumando todos los números primos por debajo de él, y tarde o temprano llegarás a la respuesta. Puede que sea sí, puede que sea no, pero tendrás una respuesta.

    Ahora imagínate que quieres averiguar si 1727 es la *resta* de 2 nº primos. Aquí sí que no tienes garantías de encontrar respuesta, porque tendrías que ir restando todos los nº primos desde 1727 hasta el *infinito*; igual tienes suerte y das con una solución enseguida… o igual no.

    Ahora imagínate que escribes un programa de ordenador para calcular ambos tipos de problemas. ¿Habría alguna forma de averiguar a priori si el problema que estás resolviendo va a tener solución en un tiempo finito o no? ¿Podrías escribir otro programa de ordenador que analice el primer programa, para saber si tendrá solución?

    Lo que dice el teorema de Church-Turing es que no, no se puede escribir un programa de ordenador para saber a priori esto.

    Lo que dice la tesis de Church-Turing es que, para el primer tipo de problemas (los que tienen solución en un tiempo finito), todos los pasos que uno seguiría para hacer esa comparación (saber si un número es primo, sumarlo con otro primo, comparar, volver a empezar si no, etc.) se pueden representar en una máquina de Turing.

    ¿Qué implicaciones tiene esto? (Esta parte ya es mía). Puesto que todas las operaciones que siguen los ordenadores actuales se pueden simular en una máquina de Turing, eso significa que un ordenador puede realizar operaciones y cálculos, pero no puede «examinarse a sí mismo» para saber si el programa que está ejecutando tiene solución. Tampoco puede resolver problemas matemáticos como el famoso teorema de Fermat. De ahí puedes extraer tus propias teorías filosóficas sobre la diferencia entre hombre y máquina, sobre qué es eso que llamamos «inteligencia» y por qué los ordenadores no la tienen, etc.

    De verdad, no sé qué hago escribiendo esto aquí, pudiendo estar de copas y ligando con bellas turistas extranjeras.

  5. Luke Abbot dice:

    Un artículo cojonudo, qué mejor manera de Juan Font para estrenarse en politikon 🙂

    Para los que se pierdan con tanta formalización, creo que lo más importante son quizás los dos últimos párrafos del artículo, así como el artículo de Denett. Y lo que dice PaulJBis sobre las limitaciones de los ordenadores.

  6. Jaime dice:

    Esta máquina de Turing es preciosa, y creo que el vídeo ilustra bastante bien cómo funciona…

    http://www.youtube.com/watch?v=E3keLeMwfHY

    La idea fundamental es que la Máquina de Turing, a pesar de ser muy sencilla, es capaz de realizar cualquier algoritmo que sea computable. Como detalle práctico, los lenguajes de programación se definen como «Turing-completo» si son capaces de simular la Máquina de Turing (y, por tanto, realizar cualquier algoritmo) o si no lo son y, por tanto, están limitadas. Estos últimos (que son bastante corrientes, por cierto) suelen ser lenguajes específicos para realizar algo en particular. Los primeros son teóricamente capaces de hacer lo que sea, resulte práctico utilizarlos o no…

  7. La Maceta Universal dice:

    Por lo que he visto en la Wikipedia en inglés y por lo que me han comentado por ahí, no estaba muy claro que Turing se suicidara. Nunca dejó nota de suicidio y por lo visto su familia lo consideraba como una muerte accidental. Aunque accidentalmente es difícil que alguien se come una manzana con cianuro….

    • Epicureo dice:

      Lo de la manzana puede ser verdad o una leyenda, pero lo que es seguro es que prácticamente lo asesinaron.

  8. Buen artículo. Yo habría hablado algo menos de autómatas y lenguajes formales, que es un enfoque quizá demasiado teórico, y habría explicado un poco mejor el concepto de máquina de estados, que tiene una relación más directa con la máquina de Turing. Y algo sobre la máquina universal, quizá lo más fascinante del tema.

    Molaría otro artículo enlazando con el tema de NP-completitud que salió en la reseña de Red Plenty de Roger, y de lo que supone para los sistemas de planificación central.

    • Kiko Llaneras dice:

      Es verdad, tenemos pendiente escribir sobre métodos de optimización (programación lineal y hermano mayores).

      Conectarlo con los sistemas de planificación, a la Red Plenty, es una opción. Por cierto, que la cuestión de complejidad NP es una dificultad, pero no la única; mi impresión es que la mayor dificultad está formular el problema, sobre todo por que hace falta una cantidad ingente de información sobre los recursos necesarios.

  9. Juan Lugo dice:

    Vaya coñazo de artículo

    • Zhurrer dice:

      Es un copia pega de cualquier curso de autómatas de ingeniería, ni más ni menos.

      • Kiko Llaneras dice:

        Entiendo que el texto te puede gustar más o menos, pero piensa que decir que lo hemos copiado es ofensivo para los que nos hemos tomado el tiempo de escribirlo. Además que sabes que no ha sido así.

Comments are closed.