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