Autómatas y maquina de turing.

Autómatas:

Los autómatas son una representación formal que permite modelar el comportamiento de diferentes dispositivos, máquinas, programas, etc. La idea general consiste en modelar un sistema que recibe un conjunto de elementos de entrada (estímulos), realiza algún proceso (cómputo) y produce una salida.

Éstos se clasifican en deterministas y no Deterministas:

• Deterministas: Cada combinación (estado, símbolo de entrada) produce un solo estado (máquina de Turing).

• No Deterministas: Cada combinación (estado, símbolo de entrada) produce varios estados y además son posibles las transiciones con λ.

Un ejemplo de autómata sería la máquina expendedora de refrescos.  Su algoritmo inicia con la necesidad del elemento de entrada (dinero) en caso de que el elemento de entrada no cumpla con la condición impuesta (monto), existe una salida que lo devuelve al presionar un botón. Si el elemento de entrada cumple con la condición, procesa la orden que se le da (¿qué producto queremos?) y entrega como salida una acción que liberará el producto deseado.

Máquina de Turing:

El concepto de algoritmo como un conjunto de pasos lógicos y secuenciales para solucionar un problema fue implementado en 1936 por Alan Turing, en la máquina de Turing. Ésta se integra de tres elementos: cinta, cabeza de lectura-escritura y programa. Una de sus propiedades es que la cinta es infinita del lado derecho y finita del lado izquierdo.

Como ejemplo, podemos tomar el algoritmo que multiplica cualquier número binario por 2 (por su misma base). El cabezal leerá, en el estado en el que esté, el valor que tenga la cinta (0, 1 o en blanco). Si el valor es 1 o 0, se recorrerá a la izquierda, lo escribirá en la cinta y avanzará al siguiente estado.

Referencias:

Olmos Pineda, Iván (s.f.) Autómatas deterministas, consultado de:

http://www.cs.buap.mx/~iolmos/propeLogica/4_Automatas1.pdf  [06/03/2017]

Apunte electrónico, Unidad 1 (s.f.), Fundamentos de algoritmos, consultado de: http://132.248.164.178/distancia/informatica/pluginfile.php/13596/mod_resource/content/1/LI_1164_13046_A_Ana%CC%81lisis%2C%20Disen%CC%83o_Implantacio%CC%81n_Algoritmos.pdf  [07/03/2017]

...