3. Modelos formales de computación: autómatas y máquinas

Teoría de autómatas

Esta teoría provee modelos matemáticos que formalizan el concepto de computadora o algoritmo de manera suficientemente simplificada y general para que se puedan analizar sus capacidades y limitaciones. Algunos de estos modelos juegan un papel central en varias aplicaciones de las ciencias de la computación, incluyendo procesamiento de texto, compiladores, diseño de hardware e inteligencia artificial.

Los tres principales modelos son los autómatas finitos, autómatas con pila y máquinas de Turing, cada uno con sus variantes deterministas y no deterministas. Los autómatas finitos son buenos modelos de computadoras que tienen una cantidad limitada de memoria, los autómatas con pila modelan los que tienen gran cantidad de memoria pero que solo pueden manipularla a manera de pila (el último dato almacenado es el siguiente leído), y las máquinas de Turing modelan las computadoras que tienen una gran cantidad de memoria almacenada en una cinta. Estos autómatas están estrechamente relacionados con la teoría de lenguajes formales; cada autómata es equivalente a una gramática formal, lo que permite reinterpretar la jerarquía de Chomsky en términos de autómatas.

Automatas

Basicamente un algoritmo autómata consiste en estados y transiciones.

 

Transiciones

• Cuando de un estado hay múltiples transiciones posibles, la máquina recibe como entrada símbolos de un alfabeto.
• El símbolo recibido determina la transición a realizar.
• Cuando hay solamente una transición posible por estado, el alfabeto es unario.
• Si una entrada causa que el autómata llegue a un estado terminar, su operación acaba.
• El resultado de la operación es el estado final elegido.

Autómatas Deterministas
Una sola transición posible de cada estado por símbolo del alfabeto, no más.

 

Autómata No Determinista

• Cuando hay dos o más posibles transiciones de un estado que usan el mismo símbolo del alfabeto, el autómata elige su transición al azar.
• La presencia de aleatoriedad se llama no determinismo.

 

Maquina de Turing
En matemáticas se considera que un método o procedimiento es efectivo para obtener un resultado cuando se cumple que:

• El procedimiento puede ser expresado mediante un algoritmo (un número finito de instrucciones concretas 1.2.1); en el que cada instrucción puede ser expresada por un número finito de símbolos.
• El procedimiento puede ser seguido sin error para conseguir el resultado en un número finito de pasos.
• El procedimiento puede ser (al menos teóricamente) seguido por un humano sin más ayuda que un papel y lápiz.
• El procedimiento no exige ninguna habilidad o inteligencia especial por parte de la persona que lo ejecuta. En lenguaje coloquial diríamos que "hasta un tonto podría hacerlo". La idea es que solo haya que seguir ciertas reglas de forma mecánica. Por esta razón cuando se cumplen estas condiciones se dice que el procedimiento es efectivo o "mecánico".
• Es una especie de autómata.
• Es el modelo más comúnmente utilizadoen la teoría de la computación.
• Es necesario para poder entender los conceptos de la complejidad computacional.

En realidad la máquina de Turing es una abstracción matemática que un dispositivo físico o mecánico.
El hecho que se le denomine "máquina" se debe a que su funcionamiento puede ser descrito en términos de operaciones individuales muy sencillas que sugieren una implementación real muy simple, lo que ha motivado que existan muchas versiones prácticas del mismo.

Ejemplo de la Maquina de Turing
Un ejemplo del proceso de esta máquina puede ser el que se muestra a continuación.
Como el número de pasos de cómputo hasta que la máquina se detiene, depende de la cantidad inicial representada en la cinta, para hacer el ciclo más breve supondremos que hay un 2 (110000...).
Los pasos ejecutados por el autómata para realizar el proceso se muestran en la tabla inferior.
La información contenida en la cinta para cada paso es la existente "antes" de la ejecución del ciclo correspondiente.
El carácter en negrita indica la posición de la cabeza en el momento de la lectura.

• P1:La máquina ejecuta el primer paso.Arranca en el estado e0, donde lee un 1; entonces, de acuerdo con su tabla de acción escribe un 0 en esa posición, se mueve a la derecha y entra en estado e1.
• P2:En e1 lee un 1, escribe un 1 y se mueve a la derecha. Sigue en e1.
• P3:En e1 lee 0, escribe 0, se mueve a la derecha y cambia a e2
• P4:En e2 lee 0, escribe 1, se mueve a la izquierda y cambia a e3
• P5:En e3 lee 0, escribe 0, se mueve a la izquierda y cambia a e4
• P6:En e4 lee 1, escribe 1, se mueve a la izquierda y sigue en e4
• El proceso sigue la misma lógica a travésde los sucesivos pasos hasta llegar al último.
• P15:En e0 lee 0; no existe ninguna entrada en la tabla para esta combinación, porlo que el autómata se detiene. Comprobamos como al final ha escrito en la cintala cantidad esperada: 11011.

 

 Operación de la máquina
Al inicio, en la cinta está el símbolo de inicio seguido por la entrada que es una cadena de símbolos del alfabeto.
La máquina está en el estado inicial y la cabeza lector está encima del símbolo de inicio.
La máquina lee el símbolo debajo de la cabeza lector y luego ejecuta a la función de transición que causa que la cabeza reemplaza el símbolo con el símbolo determinado y luego mueve según la dirección de puntero determinada.
Cuando la máquina llega a un estado terminar, la cadena que está escrita en su cinta es la salida de la máquina.

Fuente: Presentacion en PowerPoint  "Modelos forales de computacion" de la M.C. Blanca Idalia Martinez Cavazos