图灵机是一个由数学家图灵在1936年构想出来的虚拟的机器，这个机器的伟大之处在于:
它非常的简单，但是它可以模拟任何的计算机程序。
它的结构
- 一条存储带
- 双向无限延长
- 存储带上有一个个小方格
- 每个小方格里面存储一个符号(数字、字母等等)
- 一个控制器
- 可以存储图灵机当前自身的状态
- 包含一个读写头，可以读、写存储带上方格里面的内容
- 可以根据督导的符号，改变自身的状态
- 读写头可以沿着存储带一格一格的左移或者右移
这里存储带其实就相当于现在计算机的内存，控制器其实就相当于CPU + 程序代码
一直听说最早的计算机程序都是通过纸带打孔的方式表示的，原来是从图灵机这里来的啊。
它的工作过程
- 准备
- 存储带上符号的初始化(准备输入数据)
- 控制器设置好自身当前的状态(程序代码的初始化)
- 读写头置于存储带的起始位置(初始化)
- 反复执行以下工作直到停机
- 读出存储带上当前方格的符号
- 根据自身状态和读入的符号，找到相应的程序语句
- 在存储带上写入相应的值
- 修改图灵机自身的状态
- 根据程序的定义把存储带左移或者右移
一个图灵机工作示例
那么图灵机如何进行实际的计算呢？我们来举个例子:
假设我们
存储带上的数据只有两种可能0,1, 图灵机负责把0变成1，1变成0。
假设我们的存储带上的数据是这样的:
我们图灵机的控制逻辑是这样的:
| 读取到的符号 | 写存储带的动作 | 移动操作 |
|---|---|---|
| 0 | 1 | 向右移动 |
| 1 | 0 | 向右移动 |
这其实就是我们的
代码。
现在我们图灵机开始运作，第一个读到0, 根据控制逻辑表，我们把它改成1，并且存储带向右移动:
这次我们读到的是1, 根据控制逻辑表，我们把它改成0，并且存储带向右移动:
继续上面的逻辑，最终读到一个空数据，图灵机执行结束。存储带最终的状态是:
最终的状态也就是程序运行的结果。
图灵完备
A computational system that can compute every Turing-computable function is called Turing-complete (or Turing-powerful). Alternatively, such a system is one that can simulate a universal Turing machine.
也就是说如果一个指令集或者程序语言能够模拟图灵机的所有能力，那么它就是图灵完备的。
这里强调的是指定的计算系统的能力是图灵机的超集
图灵等价
A Turing-complete system is called Turing equivalent if every function it can compute is also Turing computable; i.e., it computes precisely the same class of functions as do Turing machines. Alternatively, a Turing-equivalent system is one that can simulate, and be simulated by, a universal Turing machine. (All known Turing-complete systems are Turing equivalent, which adds support to the Church–Turing thesis.)
一个计算系统被称为图灵等价的前提是它是图灵完备的。但是这还不够，它的所有的能力，图灵机也要具备。
这里强调的是指定计算系统的能力跟图灵机的计算能力是一样的。
