图灵机的极简实现
图灵机是英国数学家图灵于 1936 年提出的一种将人的计算行为抽象化的数学逻辑机，其更抽象的意义为一种计算模型，可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。
基本思想
图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作：
- 在纸上写上或擦除某个符号；
- 把注意力从纸的一个位置移动到另一个位置；
而在每个阶段，人要决定下一步的动作，依赖于此人当前所关注的纸上某个位置的符号和此人当前思维的状态。为了模拟人的这种运算过程，图灵构造出一台假想机器，该机器由以下几个部分组成：
- 一条无限长的纸带(tape)，纸带由很多个格子构成，用于输入输出信息。每个格子中包含一个来自有限字母表的符号，字母表中有一个特殊符号表示空白。纸带上一端的格子从 0 开始编号，另一端无限延伸一直到无穷大。
- 一个读写头(head)，读写头可以在纸带上左右移动，它能读出当前所指的格子上的符号，并能改变当前格子上的符号。
- 一套控制规则(table)，根据当前机器状态和纸带内容来确定下一步的动作：
- 写入或擦除当前格子内容
- 移动读写头，向左、向右、或不动
- 保持当前状态或转移到另一状态
- 一个状态寄存器(state register)，用于保存机器状态。图灵机的状态个数有限，并且有一个特殊的状态：停机状态。
图灵完备
只要能模拟单带图灵机，就是图灵完备(递归可枚举)的。这意味着其计算能力与通用图灵机等同。不是图灵完备的情况:
- 递归或循环有限，无法写不终止的程序(如 while(true){})
- 不能模拟无限长纸带(没有足够的空间来完成计算)
但图灵完备也有可能带来坏处，有些场景我们需要限制语言的表达能力，通过限制无限循环却保程序一定是可终止的。
极简实现
Brainfuck 是一种极小化的图灵完备的程序语言，它仅由八种运算符构成。
它的工作机制与单带图灵机高度一致，它用一个一维数组存取数据，数组元素初始化为 0。此外，有一数据指针，每一时刻都指向数组的某一元素。指针可以向左/右移动，也可以读取/修改当前值。如果你了解 C 语言，那么一看表格便明白它每个运算符的含义：
| Brainfuck | C |
|---|---|
> |
++ptr; |
< |
--ptr; |
+ |
++*ptr; |
- |
--*ptr; |
. |
putchar(*ptr); |
, |
*ptr = getchar(); |
[ |
while (*ptr) { |
] |
} |
不了解也没关系，它每个运算符的含义如下：
>指针右移一格<指针左移一格+使指针当前格数值加一-使指针当前格数值减一.把当前格数值按 ASCII 表输出到终端,从终端接收一字节的数据，存储其 ASCII 数值到当前格[当指针当前值为 0 时，程序跳转至与之对应的]之后；否则程序正常执行]程序跳转回与之对应的[处
有了这些工具，我们可以很快写出一个计算乘法的程序。因为 ASCII 表中 ‘A’ 对应的值为 65，可以使用 5 * 13 算出 65 并输出得到字符 ‘A’。
|
|
把 Brainfuck 的一维数组命名为 arr，则开始的数组元素为 arr[0]，arr[0] 右边的数组元素为 arr[1]。第一句代码将 arr[0] 的数值递增 5 次变为 5。
然后，循环执行“右移指针，递增 13 次，左移指针，递减 1 次”。当 arr[0] 的值最终被递减为 0 的时候，循环结束。此时 arr[1] 的值执行了 5 次“递增 13 次”的操作，即 65。最后指针右移至 arr[1]，输出它对应的 ASCII 值即为 A。