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 unagramática
formal, lo que permite reinterpretar la jerarquía
de Chomsky en términos de
autómatas.
Existen muchos otros
tipos de autómatas como las máquinas de acceso aleatorio, autómatas
celulares, máquinas ábaco y las máquinas de estado abstracto; sin embargo en
todos los casos se ha mostrado que estos modelos no son más generales que la
máquina de Turing, pues la máquina de Turing tiene la capacidad de simular cada
uno de estos autómatas. Esto da lugar a que se piense en la máquina de Turing
como el modelo universal de computadora.
Todo algoritmo evalúa una correspondencia f
: D ! S
donde D son los datos y S las soluciones.
Un problema es una correspondencia f
: D ! S entre
dos conjuntos. Resolver un problema es evaluar f .
Un problema f
: D ! S es susceptible de ser resuelto
solamente si D y S son lenguajes expresables sobre un
alfabeto finito. Uniendo alfabetos, uno podría suponer que
son lenguajes sobre un alfabeto común
Un problema es, por tanto, evaluar una correspondencia
f
: ! . Los elementos del dominio (los datos) se
suelen llamar inputs (también son susceptibles de ser
llamados inputs aquellos x
2 tales que no existe f (x)).
Los elementos del rango de f son las soluciones y se
denominan outputs.
No hay comentarios:
Publicar un comentario