计算机的理论模型——图灵机

1. 图灵机的由来

图灵机 由英国数学家 阿兰·麦席森·图灵（Alan Mathison Turing） 于1936年提出的一种抽象的计算模型，即一切可计算问题都可以由一个虚拟的机器代替人类进行计算。

图灵机的概念在《论数字计算在决断难题中的应用》中提出，原论文题目为《On Computable Numbers, with an Application to the Entscheidungsproblem》，链接https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf

可计算问题

定义：设函数f的定义域是D，值域是R，如果存在一种算法，对D中任意给定的x，都能计算出f(x)的值，则称函数f是可计算的

研究思路：为计算建立一个数学模型，然后证明，凡是这个计算模型能够完成的任务，就是可计算的任务

2. 图灵机的构成

（1）一条存储带

双向无限长

上面有一个个小方格

每个小方格可以存储一个数字/字母

（2）一个控制器

可以存储当前自身的状态

一个读写头，可以读、写存储带上小方格的数字/字母

可以根据读写头读到数字/字母和程序更改自身的状态

可以沿着存储带一格一格地左移或右移

3. 图灵机的工作步骤

3.1 前期准备工作

初始化存储带上的符号

设置控制器当前自身的状态

放置读写头于起始位置

准备好工作程序

3.2 工作流程

读写头读出存储带上当前方格中的数字/字母

根据自身当前的状态和读到的字符，找到相应的程序语句；

根据相应的程序语句，做如下三个动作：

在当前存储带的方格上写入一个相应的数字/字母

变更自身状态

读写头向左或向右移动一步，或保持不变

4. 头脑风暴 - 模拟图灵机工作

4.1 图灵机的程序构成

图灵机的程序可以由五个元素为一组的序列定义：

<q, b, a, m, q'>

q：当前状态

q'：下一个状态

b：当前方格中的符号

a：当前方格中修改后的符号

m：读写头移动的方向，左移L（Left），右移R（Right），保持不动H（Hold）

举例说明：<q1, 1, 0, R, q2>，当前状态为q1，读写头所在的方格内容为1，需要做如下三个动作：

将方格的内容改为0

变更自身状态为q2

读写头向右移动一格

4.2 用图灵机来计算

图灵机运行前的准备工作：

存储带上的符号初始化，当前字母表为

设置控制器当前状态为q1，状态集合为

读写头置于起始位置

准备好起始程序

图灵机开始工作：

读到的数据为 1，当前的状态为q1

满足的程序如下，执行的动作为：

小方格中写入 1

状态保存不变，仍为q1

读写头向右移动一格

此时，图灵机 成功停机 ，完成计算。

仔细分析，该步骤就是将 左边的3个“1” 和 右边的 2个“1” 相加， 得到5个“1” ，即完成 3 + 2 = 5 的计算。

该图灵机在进行任意两个大于0的整数相加。

5. 图灵机的重要性

5.1 图灵机的特点

图灵机样机设计参考

5.2 图灵机的理论意义

给出了一个可实现的通用计算机模型

引入了通过“读写符号”和“状态改变”进行运算的思想

证实了基于简单字母表完成复杂运算的能力

引入了存储区、程序、控制器等概念的原型