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.