Tópicos Ciencia e investigaciones

Máquina de Turing: qué es y cómo funciona

No podemos concebir el momento histórico en el que habitamos sin reparar en la importancia de la informática. En apenas unos pocos años ha pasado de usarse en ámbitos específicos a ser un ente omnipresente, y no únicamente en los ordenadores, sino también en los teléfonos móviles y en casi todas las tecnologías de uso común (como los llamados "wearables").

De hecho, el ordenador o móvil que usas para leer este artículo cuenta con tal tecnología que hace escasas décadas hubiera necesitado un espacio enorme para funcionar (o habría sido totalmente inviable). Y es que hoy avanzamos hacia una extraordinaria miniaturización de los componentes informáticos, lo que ampliará su uso y facilitará su expansión a toda área de la vida.

El avance al que nos somete la tecnología es imparable, hasta el punto de que sin ella ya no podríamos vivir de una forma óptima. Nuestra especie depende de la informática, porque la sociedad actual es de tal complejidad que las funciones cognitivas desnudas ya no permiten gestionarla con éxito, requiriéndose una ayuda externa para compensar nuestras carencias.

En este texto veremos en qué consiste el concepto de la máquina de Turing, creada a mitad del siglo 30. Su contribución a la informática tal y como se conoce hoy es evidente, considerándose el modelo sobre el que se cimientan la lógica y la arquitectura de los actuales ordenadores. Esto es: la madre de una tecnología que no solo ha cambiado el mundo, sino también el horizonte de la humanidad.

¿Qué es la máquina de Turing?

La máquina de Turing es un dispositivo creado en 1936, que representa un modelo idealizado de computación capaz de almacenar/procesar información virtualmente infinita. El sistema es una abstracción matemática que se construye de un modo extraordinariamente sencillo, pero que facilita la comprobación empiricista de un abanico amplio de preguntas sobre las teorías de la computabilidad y/o de la complejidad. Su ideación marcó un gran hito en la historia de la informática, hasta el punto de ser considerada como el origen de los actuales ordenadores (y de las tecnologías afines, como las tabletas o los teléfonos móviles).

El artífice de esta fue Alan M. Turing, lógico y matemático inglés que pretendió toda su vida la concepción de un modelo teórico con el que dar respuesta a las incógnitas de su disciplina, de forma automática y accesible a todos.

Este genio británico, cuya importancia histórica no se puede cuestionar, contribuyó también (junto a varios científicos polacos) a desentrañar los códigos criptografiados que los militares nazis usaban para comunicarse secretamente entre ellos durante la triste segunda guerra mundial (a través de lo que se conoció como máquina enigma). Para ello ideó un dispositivo de corte electromagnético (bombe), cuyo uso acortó la duración del conflicto y salvó innumerables vidas humanas, al permitir que se desvelaran los planes del régimen durante el tiempo que se prolongaron las hostilidades.

La máquina de Turing es el precursor histórico de los modernos "computadores de programa almacenado", que permiten tanto el guardado de los datos como de los algoritmos sobre los que estos se construyen. Su ventaja, y uno de los factores por los que genera fascinación en los teóricos del cómputo, es su sencillez y sus enormes posibilidades de configuración a nivel técnico; y es que posibilita la experimentación a través de cómo se dispongan sus elementos físicos y se plantee la "pregunta" con la que se programa su uso (mediante algoritmos, que se traducen en una "sucesión" de códigos que se inspiran en el lenguaje lógico). Esta capacidad tan versátil obedece a la naturaleza misma de los datos con los que opera, sujetos a un nivel de abstracción enorme.

De esta manera, la máquina de Turing puede ser programada para ejecutar instrucciones de carácter concreto, que respondan a preguntas más o menos complejas. Todo ello implica que se debe conocer su particular lenguaje, con el objetivo de adaptar a este el algoritmo para su funcionamiento, conscientes de que no existe un código universal para clarificar la totalidad de las incógnitas matemáticas que dormitan en la naturaleza misma (como indica la ley de Church-Turing). Por tanto, el sistema requiere una mente humana detrás, que se pregunte a sí misma la duda a formular y que sepa cómo ha de "dirigirse" al dispositivo para resolverla.

La materia prima de la máquina de Turing son los números computables, esto es, los que se pueden calcular de manera objetiva mediante una fórmula matemática, y en el umbral de un tiempo razonable. En este contexto, es básico que se adapte a dos "problemas" concretos: el de la decisión (cada respuesta está precedida por una serie de elementos de cálculo previos que pueden ser respondidos dicotómicamente como sí/no) y el de la parada (reconocer si las respuestas finales son realmente posibles, o si el sistema quedará "condenado" a procesar la orden en un ciclo infinito/irresoluble). Esto es, que exista un algoritmo concreto para aquello que se pretende conocer y que su tecnología lo pueda responder con la precisión necesaria para "detenerse" y ofrecer una solución.

Hasta este punto se han tratado en detalle las lógicas teóricas de una máquina de Turing. En las próximas líneas se ahondará en el núcleo de sus particularidades físicas y/o funcionales, con las cuales podrá ejecutarse el algoritmo o norma de funcionamiento que el usuario haya dispuesto (y que puede oscilar desde sencillas ecuaciones a las entrañas mismas de la ley de la abstracción matemática).

Descripción de la máquina de Turing

Junto al fundamento lógico/matemático que se ha descrito, la máquina de Turing requiere una serie de elementos físicos, los cuales tienen la función de ejecutar los comandos introducidos con anterioridad. La disposición de los mismos puede ser diversa, pues existirían casi infinitos diseños de este sistema, pero se requieren los siguientes necesariamente: una cinta de papel o de un material similar, un cabezal móvil cuyo extremo es capaz de realizar trazos (símbolos o números) y un procesador central en el que codificar los algoritmos que se requieran o que faciliten el análisis.

La cinta es el elemento más esencial de todos ellos. No es más que una tira longitudinal, que se divide en una sucesión de cuadros de igual tamaño (o casillas), y cuya longitud dependerá en gran parte del "esfuerzo" que deba llevarse a cabo para solventar la pregunta que plantea el usuario (pudiendo ser tan corta o tan larga como se estime pertinente). Las casillas están reservadas para que el cabezal trace símbolos distintos (como el 0-1 en el código binario) en cada una, y constituyen el producto de cálculo que habrá de ser comprobado tras su parada. En términos informáticos, estas cintas podrían ser la memoria de un ordenador moderno. Las primeras celdas suelen tener un contenido ya establecido (input), quedando el resto vacías y preparadas para ser ocupadas tras el proceso de computación.

Asímismo, la máquina de Turing consta de un cabezal, un apéndice mecánico (móvil) que se desplaza a la izquierda o la derecha siguiendo la orden que el sistema dispone para él. En su extremo cuenta con una elongación capaz de grabar un trazo sobre la cinta, dando su forma a los números o las figuras que correspondan según el código que determina el movimiento. El modelo original contaba con un cabezal de tecnología rudimentaria, pero el avance en los ámbitos de la robótica ha permitido la irrupción de nuevos diseños más avanzados y precisos. El cabezal "lee" los contenidos de las celdas y se desplaza una única casilla a cualquiera de sus lados (según cuál sea su estado concreto) para seguir ejecutando la instrucción.

En tercer lugar, existe un procesador central al que se destina la función de almacenar código y algoritmos que contienen instrucciones para la actividad del aparato, expresadas siguiendo términos matemáticos y lógicos. Este lenguaje tiene un matiz universal, aunque permite cierto grado de maniobra para introducir expresiones operativas formuladas por el usuario (siempre que haya operativizado el significado). De esta manera, su cabezal facilitaría la ejecución de instrucciones almacenadas en el procesador, que equivaldrían a lo que hoy se conoce como programas o aplicaciones (app). Este sistema permitiría reproducir cualquier cálculo posible y se alzaría como el predecesor de cualquiera de los ordenadores actuales.

Funcionamiento de este dispositivo

Una máquina de Turing está diseñada para el grabado de una muestra concreta de símbolos o números, cuyo universo posible suele recibir el nombre de "alfabeto". Cuando funciona con código binario, su alfabeto total es de dos (0 o 1), pero puede ser tan amplio como se estime adecuado para la función a realizar. El cabezal solo podrá reproducir en las celdas de la cinta aquello que se haya señalado previamente en tal sistema, por lo que un cálculo (número "pi", por ejemplo) requerirá el espectro completo de números (de 0 a 9).

Además de esto, suele contemplarse también lo que en la práctica se conoce como estados (Q), los cuales también son programados por el usuario durante la descripción del código (y que se etiquetan como q1, q2, q3, q4… qn). El rango total depende de hipótesis matemáticas abstractas, y reseña los matices condicionales de la fórmula lógica del código, con la finalidad de que el cabezal se desplace en la dirección que corresponda y realice la acción pertinente ("si te hayas en la posición q2, escribe "0" y no te muevas", p.e.).

Por último, existiría una función de "transición" (delta), en la que se resume la secuencia total (paso a paso) del procesamiento matemático, y que expresa la instrucción completa: lectura de celda, escritura de nuevo símbolo, cambios de estado (o no) y movimiento del cabezal; en un ciclo recurrente que se detiene al encontrar la respuesta a la pregunta inicial, o también en el momento en que el usuario lo haya previsto dentro de su código (a menudo mediante una exclamación, que se lee como "parada"). En el momento en que la máquina para de moverse, se recupera la cinta y se analiza al detalle qué respuesta ha proporcionado.

Como puede apreciarse, existe clara similitud entre la máquina de Turing y los ordenadores que usamos hoy en día. Su aportación ha sido clave para avanzar exponencialmente en todo diseño informático posterior, hasta el punto de que su espíritu reside en el corazón mismo de una tecnología que nos permite mantenernos interconectados.

Referencias bibliográficas:

  • Khan, S. y Khiyal, M. (2006). Turing Model for Distributed Computing. Information Technology Journal. 5, 305-313.
  • Qu, P., Yan, J., Zhang, Y. y Gao, G. (2017). Parallel Turing Machine, a Proposal. Journal of Computer Science and Technology, 32, 269-285.