学过计算机课程的人，大概第一节课老师就会讲图灵，图灵也被成为计算机之父。他是英国计算机科学家、数学家、逻辑学家、密码分析学家和理论生物学家。他还提出了一种数学模型，图灵机模型；图灵机（Turing Machine，TM）又称确定型图灵机，它是一种抽象的计算模型。其更抽象的意义为一种数学逻辑机，可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。1 他的基本思想就是来，模拟人们用纸和笔进行数学计算的过程，我们可以把这样的过程定义为以下的两个步骤：

现在来给图灵机模型增加一些定义：

上述的这些定义就构成可图灵机模型的所有场景了；图灵机是强大的。Church–Turing thesis认为：“ 任何在算法上可计算的问题同样可以由图灵机计算“

上面简单介绍了以下图灵机的基本概念，我们也使用了Church–Turing thesis来说明图灵机的强大，既然他这么强大，说骡子是马拉出来遛遛，所以这里我们就把图灵机应用到一个例子中。 Example 1: 把纸带上存储的值加1（使用二进制来表示的无符号整数）:

现在我们来定义我们的算法：

接下来我们就用一个表格来表示这样的一个移动状态（表达式的状态放到第三列和第四列了）：

在这里我们可能会有这样的疑问，当我们在第七步的时候我们已经完成了数值加一的操作为什么还要去进行后面的步骤呢，这个就涉及到算法的初态和终态的概念，当我们下次再去这样运行加一操作的时候，就可以在上一次的终态的基础上进行操作了。这样就方便了算法的复用性

在计算复杂性理论内，随机存取图灵机(random-access Turing machines)是一种变版的图灵机，用来处理大小较小的复杂度类，特别是使用对数时间的复杂度类.在随机存取图灵机上，多了一个特殊的指针磁带，大小是对数空间，字母是二进位单字(0和1)。图灵机有一个特殊的状态(state)，当指到这个状态而指针磁带的数字(二进位)是’p’时，图灵机会将工作磁带上面的指针移动到输入的第p个符号。 这特性让图灵机可以直接读取输入的特定字母，而不需要花时间去处理整条输入。这对使用少于线性时间的复杂度类来说，是必要的(因为处理整个输入的时间是线性时间)2

RAM模型的定义：