Si alguna vez te preguntaste ¿Cuál fue el origen o el inicio de todo lo que hoy conocemos como la informática o computación? No te diremos que fue el creador de una computadora ni el creador de Windows, hoy te hablaremos de Alan Turing y su Máquina universal.
Alan Turing fue un matemático, lógico, informático e investigador en el área de criptoanálisis. Sus contribuciones varían desde el campo de la lógica-matemática hasta lo que hoy en día conocemos como informática. Uno de sus mayores logros fue lo que hasta hoy conocemos, y que sigue siendo objeto de estudio, la Máquina de Turing.
¿Cuál es la idea de una Máquina de Turing?
La idea en general de lo que es la Máquina Turing se puede resumir de la siguiente manera: Es una abstracción lógico-matemática que logra capturar la noción o idea de lo que es un algoritmo, es decir, es la idea base de lo que es tener una serie de reglas o procesos para resolver determinadas tareas o problemas.
Poniéndonos más en contexto, la idea de la Máquina de Turing (1936) surge a partir de otro problema en Lógica Formal, a saber, si era posible tener un método o una serie de reglas que pudieran determinar para cualquier sentencia, teorema o fórmula matemática si era cierta o no y con ello tener una prueba de tales sentencias, teoremas o fórmulas. Éste problema fue planteado por David Hilbert y Turing demostró por medio de su máquina (el lenguaje de la Máquina de Turing) que no existía tal procedimiento (cabe resaltar que fue primero Kurt Gödel (1931) quien ya había respondido a tal cuestión con los teoremas de la incompletitud, Turing sólo reformuló los teoremas en términos de computabilidad).
La idea de la Máquina de Turing es que representa formalmente lo que es un algoritmo, siendo así una manera de poder ver qué tipo de problemas se pueden resolver dentro de cualquier proceso puramente mecánico. En este sentido, un modelo o proceso computacional que pueda llevar a cabo determinadas tareas se sitúa dentro de la idea base de la Máquina de Turing. Hay varios tipos de Máquinas de Turing y todas ellas engloban la idea original de Alan, el caso es que cada máquina de Turing puede representar mediante un lenguaje formal un lenguaje algorítmico computacional ¡He ahí la relevancia teórica!
¿Qué es y Cómo funciona?
Vámonos a lo divertido. Primero, una Máquina de Turing está compuesta por un cabezal (comúnmente llamado “head read/write”) y una cinta dividida en celdas donde se pueden escribir determinados símbolos. La cinta con celdas es infinita, ésta cinta puede empezar de izquierda a derecha dependiendo el input o el punto de donde partamos. El cabezal será el aparato que lea los símbolos de la cinta y, en caso de que se le pida, borrará y escribirá otro símbolo.
Ahora bien, ¿cuál es el proceso formal de la Máquina de Turing? Formalmente, la Máquina de Turing se puede definir de la siguiente manera: sea la cuadrupleta <Σ, Γ, ω, f >; Σ: sigma es el input, es decir, lo escrito en la cinta y por lo que empezaremos; Γ: gamma es el alfabeto, es decir, las letras con las que trabajará la máquina; ω: omega son los estados internos de la máquina; y f : es la función de transición, es decir, es la operación que permite a la máquina poder hacer una determinada función.
Concentrémonos en la función de transición. La función de transición es la que nos va a permitir poder generar el movimiento en la máquina, es decir, nos permite que la máquina realice sus operaciones de forma codificada y mecánica. Formalmente hablando, la función de transición se puede formalizar de la siguiente manera: f : ω × Γ => Γ × {l, r, S} × ω
La función de transición en el lenguaje humano se puede leer de la siguiente forma: Si te encuentras en un estado ‘x n’ de ω y lees ‘y’ letra del alfabeto Γ, entonces borra ‘y’ letra de Γ y escribe ‘z’ letra de Γ, muévete o bien para la izquierda (left) o bien para la derecha (right) o bien para (stop) y quédate en un estado ‘x n’ de ω.
Pongamos un ejemplo abstracto en marcha: sea Σ: 00000 ; Γ: { Δ, 1, 0} ; ω: { ω0, ω1, ω2, ω3, ω4, ω5, ω6, ω7} y la función f : ω × Γ => Γ × {l, r, S} × ω *Por comodidad, suele usarse el código binario para presentar números o resultados y usamos Δ para referirnos a espacios en blancos *
Sea que mi máquina se encuentre en un estado ω0, lee 0, deja escrito 0 y se mueve a la derecha y pasa a un estado ω0. ¡Formalicemos! f : (ω0, 0) = ( 0, r, ω0)
f : (ω1, 1) = ( 0, r, ω1) Si estas en estado ω1 y lees 1, entonces escribe 0, muévete a la derecha y permanece en estado ω1
f : (ω1, Δ) = (Δ, r, ω2) Si estás en estado ω1 y lees Δ , entonces deja Δ, muévete a la derecha y pasa al estado ω2
f : (ω7, Δ) = (Δ, S, ω7) Si estás en estado ω7 y lees Δ, entonces deja Δ, para y quédate en estado ω7
De manera recursiva podemos componer distintas funciones:
f : (ω0, 0) = ( 0, r, ω0); f : (ω0, 1) = ( 0, r, ω1); f : (ω1, 1) = ( 0, r, ω1); f : (ω1, Δ) = (Δ, r, ω2); f : (ω2, 0) = ( 1, r, ω2); f : (ω2, 1) = (Δ, l, ω2); f : (ω2, Δ) = ( 0, l, ω3); f : (ω3, 0) = ( 1, r, ω3)… f : (ω7, Δ) = (Δ, S, ω7)
Dejemos un rato la abstracción y vayamos a un caso concreto. Supongamos que vengo de la secundaria y me piden encontrar el valor de x en el siguiente ejercicio: 1x + 1 = 3. Intuitivamente sabemos que el valor de x es igual a 2, sin embargo quisiéramos poder llevar un procedimiento algorítmico en código binario que me permita realizar la multiplicación de 1×2 y que a su vez sumado con 1 me dé como resultado 3. Usemos el mismo ejemplo abstracto pero con sólo 4 estados: sea Σ: 00000 ; Γ: { Δ, 1, 0} ; ω: { ω0, ω1, ω2, ω3} y f : ω × Γ => Γ × {l, r, S} × ω. Antes, hay que saber que los primero 5 números en código binario son los siguientes: 01: 00001; 02: 00010; 03: 00011; 04: 00100; 05: 00101. Por supuesto, queremos llegar a 03, es decir, a 00011.
Como sabemos, nuestro input Σ va a comenzar con 00000, y vamos a comenzar de izquierda a derecha, es decir, del primero marcado en negrilla 00000.
00000
Multiplicar 1 por x cuando x = 2
(ω0, 0) = (0, r, ω0) y nuestro cabezal (read/write) pasa al segundo cero 00000
(ω0, 0) = (0, r, ω0) ; 00000
(ω0, 0) = (0, r, ω0) ; 00000
(ω0, 0) = (0, r, ω0) ; 00000
(ω0, 0) = (0, r, ω0) ; 00000Δ
(ω0, Δ) = (Δ, l, ω1) ; 00000
(ω1, 0) = (0, l, ω1) ; 00000
(ω1, 0) = (1, l, ω1) ; 00010
(ω1, 0) = (0, l, ω1) ; 00010
(ω1, 0) = (0, l, ω1) ; 00010
(ω1, 0) = (0, l, ω1); Δ00010
Sumar más 1
(ω1, Δ) = (Δ, r, ω2); 00010
(ω2, 0) = (0, r, ω2) ; 00010
(ω2, 0) = (0, r, ω2) ; 00010
(ω2, 0) = (0, r, ω2) ; 00010
(ω2, 1) = (1, r, ω2) ; 00010
(ω2, 0) = (1, r, ω2) ; 00011Δ
(ω2, Δ) = (Δ, S, ω3); 00011Δ !
1x + 1 = 00011 = 3
De esta manera, con el simple procedimiento mecánico logramos llegar al resultado de la fórmula 1x + 1 = 3.
Hagámonos la pregunta ¿Qué es la máquina de Turing? Como hemos visto, es un procedimiento algorítmico que puede ser hecho por medio de una máquina, pero también la forma o procedimiento formal de la Máquina de Turing representa o captura la idea formal de un algoritmo cualquiera de una computadora, lo que es igual a decir que para cualquier procedimiento algorítmico de una computadora, existe un equivalente a la Máquina de Turing. He aquí la importancia de la Máquina de Turing y el gran avance que nos permitió el mismo Alan Turing. Pues es mediante la Máquina de Turing por el que podemos estudiar los procedimientos mecánicos de un computador, sencillamente una herramienta teórica que permitió el avance del procesamiento de información y lo que hoy en día se ha vuelto parte de nuestras vidas: La Computación o Informática.
