第一章自动机：方法及其狂热自动机理论的研究对象是抽象计算装置，即“机器”。
在20世纪30年代计算机出现以前，图灵（A. Turing）就研究了一种抽象机器，这种机器具有现代计算机的所有能力，至少它们的计算能力是相同的。
图灵的目的是要精确地描述什么是计算机所能做的和不能做的。
他的结论不仅适用于他自己的抽象图灵机，也适用于今天的实际计算机。
20世纪40和50年代，许多研究人员还研究了一些更简单的机器，现在称这类机器为“有穷自动机”。
原先提出有穷自动机是为了建立人脑功能的模型，但后来发现它对其它许多目的也十分有用。
第1.1节将提及这些目的。
还是在20世纪50年代后期，语言学家乔姆斯基（N. Chomsky）开始研究形式“文法”。
文法虽然不是严格意义上的机器，但与抽象自动机有着十分密切的关系。
现在文法已被用作一些重要软件的基础，如某些编译器部件。
1969年库克（Cook）将图灵的研究扩展到什么能计算和什么不能计算。
有些问题虽然原则上计算机能解，但实际上，除了很小规模的实例外，解这些问题需要计算机花费太多的时间以至于计算机根本无能为力。
这类问题称为“难解的”或“NP-难的”。
即使计算机硬件的计算速度一直以来都呈指数级增长（摩尔（Moore）定律），但还是不会对我们解决大规模难解问题的能力产生重要影响。
库克能在难解问题中分离出计算机可有效解的问题。
所有这些理论进展对计算机科学家今天所做的事都有直接影响。
有些概念，如有穷自动机和某些种类的形式文法，已经被用于一些重要软件的设计和构造。
另外一些概念，如图灵机，则可帮助我们理解软件能做什么。
特别地，难解性问题理论使我们能够作如下的判断：是否能够“正面”地处理一个问题并且写一个程序来解之（因为它不在难解性类中），或者是否不得不拐弯抹角地处理难解性问题，如寻找近似算法、使用启发式算法，或者使用其它方法来限制程序解此问题时所花费的时间量。
本入门章首先介绍关于自动机理论的一个非常高水平的观点，再介绍它的使用者都是谁。
