El Autómata Finito
Antes de estudiar la Máquina de Turing, convendrá que exploremos su hermano pequeño, el Autómata Finito. A pesar de que sus capacidades son limitadas, este modelo es capaz de ofrecer una gran versatilidad, especialmente cuando forman una red de múltiples dispositivos.
Máquinas como modelos
Los modelos de máquina que veremos son realmente modelos matemáticos. Esto significa no solo que la implementación física es irrelevante, sino también que abstraeremos una serie de parámetros que sí son relevantes si la máquina funcionase en la “realidad”. Uno de esos parámetros es el tiempo. Como se ha dicho, todo procedimiento mecánico se realizará en una serie sucesiva de pasos discretos. No importa cuánto duren esos pasos en tiempo físico, solo que sean sucesivos y que no se solapen entre ellos. No hay transición entre pasos, el cambio será instantáneo. Así que, decimos que, si la máquina se encuentra en el paso número t, el paso sucesivo será t + 1, y el anterior t – 1.
Las máquinas de estado finito se caracterizan porque adoptan un estado y solo uno en cada momento t_{i}. Dichos estados son configuraciones que la máquina puede adoptar y que determinan el comportamiento de la máquina en el paso siguiente t_{i} + 1. Un semáforo por ejemplo tiene tres estados: rojo, verde y ámbar. Si el semáforo está en rojo en el estado t, significa que estará verde en el estado t + 1. El número de estados disponibles para el autómata será finito, es por eso que se conocen como autómatas de estado finito.
Definición formal de Autómata Finito
Como modelos matemáticos que son, necesitaremos de una definición formal del Autómata Finito. Todo Autómata Finito M queda descrito como:
Siendo Q el conjunto de estados que puede adoptar y E el conjunto de señales o alfabeto del input que puede reconocer la máquina. Esto último no es fácil de ver en el ejemplo del semáforo. Pero imagínate una linterna, sus posibles estados serán dos, Q = \left \{ encendido, apagado \right \}, y, si tiene un único botón para apagar y encender, el input reconocible por la máquina será solo uno E = \left \{ pulsar \right \}. Además de estos conjuntos, la máquina necesitará una regla de comportamiento del tipo “cuando en el estado q_{(t)} reconozcas el input e, cambia al estado q_{(t+1)}«. Esa regla la expresaremos como una función de transición δ
Vemos que, en el ejemplo de la linterna, el input y el estado del momento t determina el nuevo estado en t + 1.
Podemos hacer que la máquina, no solo cambie de estado, sino que devuelva un output cada vez que realice un paso. Siguiendo el ejemplo de la linterna, esta puede encender un pequeño led verde siempre que pase a estar encendida y rojo cuando se apaga. Eso implicaría añadir un nuevo alfabeto a la descripción de la máquina
siendo S = \left \{ verde, rojo \right \}, así como nueva función de transición:
El Diagrama de Estados
Para visualizar la operación de un Autómata Finito, suele recurrirse a un diagrama de estados. La imagen siguiente representa un Contador de Paridad, una máquina que recibe como input una cadena de 1s y 0s y reconoce si el número de 1s es par o impar según el estado final que resulte de computar toda la cadena. Cada uno de los dígitos de la cadena los computa de uno en uno, sin embargo, es capaz de contar la paridad de cadenas arbitrariamente largas.
El autómata cuenta con dos estados Q = \left \{ par, impar\right \}. El estado inicial de la máquina es par. Las flechas señalan las funciones de transición acompañadas del dígito que está recibiendo la máquina en ese momento.
Cadenas de input y Recursión
El concepto de Recursión
Vamos a introducir un concepto que exploraremos con más detalle en el futuro pero que plantearemos someramente ahora. Es el concepto de recursión.
Un algoritmo recursivo es aquel cuya operación requiere de llamarse a sí mismo. Podemos expresar algoritmos recursivos mediante funciones recursivas. Un ejemplo sería contar los números de uno en uno. Contar hasta 100 implica contar hasta 99, que a su vez implica contar hasta 98. La siguiente función recursiva ς cuenta hasta un número n.
Vemos que al definir la función hacemos uso de esa misma función.
El algoritmo recursivo es válido siempre y cuando no termine en una computación infinita. Cada paso debe acercarnos más a la resolución del problema y por tanto, este debe darse en un tiempo finito. Para evitar esto, se establece un caso base que limite el número de recursiones. En el ejemplo de la función de contar, el caso base sería ς(1) = 0 + 1 que es como decirle «cuando n sea 1 no sigas llamándote a ti mismo sino que lo sustituyas por 0«. Sin esta instrucción, el algoritmo continuaría llamándose así mismo de forma indefinida con cada número negativo.
Imagínate un algoritmo que genera siluetas de caras a partir de siluetas de caras. Ese algoritmo requerirá de un procedimiento que genere siluetas de caras, es decir de sí mismo.
Cadenas de signos como input
Los Autómatas Finitos reconocen un carácter o signo del alfabeto cada vez. Pero podemos hacer que la máquina reconozca de forma sucesiva un conjunto de signos. Este conjunto lo visualizaremos como una cadena de signos que, uno por uno, irá leyendo la máquina.
Expresaremos esto mediante dos funciones. Tras cada operación con un signo, la máquina terminará con un estado concreto. Así que la primera manifiesta la operación de un Autómata M con un input x, y el estado resultante q_{r}:
La segunda función expresará el estado final de la máquina después de computar no un solo signo, sino toda una cadena a de signos x.
Si el alfabeto de las xs fuera por ejemplo el conjunto \left \{1, 0 \right \}, una posible cadena sería (1, 0, 0, 1, 1, 0)
El Autómata Finito como función recursiva
Para señalar que a una cadena a se le ha añadido al final un nuevo signo x simplemente ponemos ax. Con estos elementos podremos expresar la operación de un Autómata Finito como una función recursiva:
Lo que expresa esta función es que el estado final tras computar toda la cadena, será equivalente a computar un único signo, el último de la cadena (x), encontrándose la máquina en el estado que resulta de computar todos los anteriores signos de dicha cadena. Así, esta función recursiva se llamará a sí misma aplicada sobre cadenas cada vez más cortas en cada iteración.
Recursión infinita
Al igual que con la función de contar, necesitamos un caso base que marcará el límite para continuar con la recursión. Evidentemente este caso será aquel en el que la cadena ya no tenga ningún signo. En lenguaje formal, una cadena vacía suele indicarse como ε.
Básicamente esta diciendo que cuando el input sea una cadena vacía, el nuevo estado de la máquina será el que ya exista.
En operaciones con Autómatas Finitos el caso base puede no ser necesario. En ausencia de bucles, la máquina computa tantas veces como signos tenga la cadena que está leyendo. Por tanto, siendo este número finito nos aseguramos que la máquina terminará en algún momento. Como veremos en el siguiente artículo, esto no es tan fácil con la Máquina de Turing. Aunque el input sea finito, una Máquina de Turing puede caer irremediablemente en una computación infinita.
Memoria del Autómata Finito
Llamamos memoria al fenómeno por el que el pasado ejerce algún tipo de influencia en el comportamiento presente o futuro de la máquina.
Las funciones de transición expresan formalmente aquello que afirmamos de que el comportamiento del autómata finito está determinado por el input y el estado del momento inmediatamente anterior. El Autómata Finito tiene por tanto una capacidad limitada de memoria, solo es capaz de “recordar” el estado e input del paso previo. Un autómata puede haber operado durante miles de pasos, pero el paso siguiente seguirá estando determinado por el inmediatamente antecedente.
Existen dos manera de solventar esta limitación. La primera es simplemente aumentar el número de estados posibles de la máquina. Podemos hacer que ante un input concreto e_{z}, la máquina adopte un estado q_{z} y lo mantenga en operaciones posteriores. De este modo, por muchas operaciones que realice, si la máquina se encuentra en dicho estado, sabremos que en algún paso previo a recibido el input e_{z}.
La segunda manera es creando un bucle, esto es, que el output de la máquina sirva también como input en el paso sucesivo. Los bucles son recursos muy útiles, especialmente cuando existen no uno, sino muchos Autómatas Finitos, conectados en una red. Para saber más sobre como funcionarían estas redes te recomendamos el artículo sobre el modelo neuronal de McCulloch-Pitts, una de las más interesantes aplicaciones de los Autómatas Finitos, germen del actual Machine Learning.
Lecturas Recomendadas
– Minsky, M. (1967) Computation. Finite and Infinite Machines.
– Feynman, R. P. (1996) Conferencias sobre computación.