Teoría De Autómatas

La teoría de autómatas es el estudio de dispositivos de cálculo abstractos, es decir, de las “máquinas”. Antes

de que existieran las computadoras, en la década de los años treinta, A. Turing estudió una máquina abstracta

que tenía todas las capacidades de las computadoras de hoy día, al menos en lo que respecta a lo que podían

calcular. El objetivo de Turing era describir de forma precisa los límites entre lo que una máquina de cálculo

podía y no podía hacer; estas conclusiones no sólo se aplican a las máquinas abstractas de Turing, sino a todas

las máquinas reales actuales.

En las décadas de los años cuarenta y cincuenta, una serie de investigadores estudiaron las máquinas más

simples, las cuales todavía hoy denominamos “autómatas finitos”.Originalmente, estos autómatas se propusieron

para modelar el funcionamiento del cerebro y, posteriormente, resultaron extremadamente útiles para muchos

otros propósitos, como veremos en la Sección 1.1. También a finales de la década de los cincuenta, el lingüista

N. Chomsky inició el estudio de las “gramáticas” formales. Aunque no son máquinas estrictamente, estas

gramáticas están estrechamente relacionadas con los automátas abstractos y sirven actualmente como base de

algunos importantes componentes de software, entre los que se incluyen componentes de los compiladores.

En 1969, S. Cook amplió el estudio realizado por Turing sobre lo que se podía y no se podía calcular. Cook

fue capaz de separar aquellos problemas que se podían resolver de forma eficiente mediante computadora de

aquellos problemas que, en principio, pueden resolverse, pero que en la práctica consumen tanto tiempo que

las computadoras resultan inútiles para todo excepto para casos muy simples del problema. Este último tipo de

problemas se denominan “insolubles” o “NP-difíciles ”. Es extremadamente improbable que incluso la mejora

de carácter exponencial en la velocidad de cálculo que el hardware de computadora ha experimentado (“Ley

de Moore”) tenga un impacto significativo sobre nuestra capacidad para resolver casos complejos de problemas

insolubles.

Todos estos desarrollos teóricos afectan directamente a lo que los expertos en computadoras hacen.Algunos

de los conceptos, como el de autómata finito y determinados tipos de gramáticas formales, se emplean en el

diseño y la construcción de importantes clases de software. Otros conceptos, como la máquina de Turing, nos

ayudan a comprender lo que podemos esperar de nuestro software. En particular, la teoría de los problemas

intratables nos permite deducir si podremos enfrentarnos a un problema y escribir un programa para resolverlo

(porque no pertenece a la clase de problemas intratables)

...