一个算法就是一个有穷的规则集，它精确地告诉我们，对于给定的一类问题，这一刻到下一刻该做什么。给定一个用来求解K类问题的算法和属于K的一个问题，任何人都能够求解这个问题，只要他能执行该算法所要求的操作，准确地遵守那些给定的规则。

在执行一个算法时，人类计算者使用一些数据，包括该算法的指令，这些数据部分地储存在他的记忆中，但更多地是写在纸上或印在参考图表上。有（a）某种存储装置来储存初始数据和居间结果。他还要执行（b）某些基本运算。他（c）通过查阅指令来决定下一步做什么，从而控制步骤序列。

在这三个要素中，（b）是最易于机械化的。台式计算器的引入已经将这方面工作的很大一部分交给了机器。自动（排序）计算机所做的是，增加（1）一个存储单元以存储信息，以及（3）一个控制单元以根据作为算法之实现的一个程序来执行指令。台式计算器被（2）一个运算单元取代，它与（1）和（3）集成在一起。起初程序是由外部通过插接板提供的，因此无法指示机器对程序进行修改以增加灵活性。但很快机器就开始拥有“存储式程序”，使得程序成为初始数据的一部分，并且可以巧妙地编写一个程序来指示机器自动完成多个程序的工作。

如果我们考虑一个人在一张纸（假设它被划分成一些方格）上做计算，该过程涉及如下几件事：（1）一种存储媒介，即那张纸；（2）一种语言，它具有表示数字和方向的符号，假定它们被写在了那张纸上；（3）被察看区域，即每个时刻被观察的一些方格；（4）“心灵状态”，即那名计算者在每个阶段都记录计算到达的阶段，并决定下一步做什么；（5）进行下一步计算的行为，它可能涉及（a）通过写下或擦除一些符号而进行的符号上的改变，（b）被察看区域的改变，（c）“心灵状态”的改变。

要使得该过程是机械的，即能被一台机器执行，或以机械的（非创造性的）方式被一个人执行，其原因可以概括为如下两个原则：A确定性原则；B有穷性原则。

根据确定性原则，在决定下一步做什么时，唯一相关的信息是当前在被察看区域观察到的符号和当前的“心灵状态”。我们可以把当前“心灵状态”设想为一种严格的、有条件的态度，即准备好做出某些特定的行为，这些行为完全取决于当前在纸上所观察到的符号。

根据有穷性原则，心灵在每个时刻只能储存和感知有穷多不同的项，这些项的数量有固定的有穷上界。每个时刻可感知项数的上界非常小，而可存储项数的上界则十分大，但相信存在这种上界仍然是合理的。由这一原则立即可得，计算者在每个时刻只能察看有穷多的方格。需要考虑的心灵状态的数量也是有穷的。可打印符号的数目也是有穷的。

计算在每一步所执行的操作涉及三类变化：心灵状态，写在计算表上的符号，以及观察区域。我们暂时假定，每次操作只进行这三种改变中的一种。

我们可以绘制在一个给定的算法下的计算的一个机械模型。每个心灵状态对应着机器的一种“配置”或状态。机器在每个时刻扫描B个方格。在每次操作中，机器可以改变其配置，或在另一个方格里改变符号，或改变所扫描区域到L个方格以内的另一个区域。把B和L限制为1并让机器在一条线状纸带上工作，无损于一般性。因此仅有的可变要素是可用符号数（字母表的大小）和状态数。我们可以通过扩充字母表来减少状态数，通过增加状态数来缩小字母表。

图灵机的定义如下。每台图灵机可以处于一个固定、有穷的状态表中的任何一个状态。它配有一张双向（潜在地）无穷的长纸带。纸带划分为一个个方格，每个方格可记写一个符号，不失一般性，可以规定方格只有空白和有标记（一次性固定下来）两种内容样态。纸带会在图灵机前经过，每个时刻，图灵机只能扫描一个方格，并处于一个给定的状态。每个时刻图灵机所扫描方格的内容（空白或有标记）和机器所处的状态，决定了该图灵机的当前配置。当前配置则决定机器要做出（或执行）什么动作（或原子行为）：改变被扫描方格的内容，或变换被扫描方格为其左侧或右侧的相邻方格（通过移动纸带或机器实现），或转变机器的当前状态为另一状态，或停机。机器从任意初始的状态和被扫描的方格开始；初始的纸带（输入）可以包含任意有标记方格和空白方格的组合，尽管通常我们假定初始纸带只包含有穷多的有标记方格。一旦启动，机器应根据其在每个阶段的当前配置进行动作。如果它一直没有机会做出“停机”的动作，它就得一直运行下去。如果机器停机了，那时纸带的内容一般称为输出。