La teoría de la computación es una rama de la matemática y la computación
que centra su interés en las limitaciones y capacidades fundamentales
de las computadoras. Específicamente esta teoría busca modelos
matemáticos que formalizan el concepto de hacer un cómputo (cuenta o cálculo) y la clasificación de problemas.
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.
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.
No hay comentarios:
Publicar un comentario