什么是图灵机
图灵机（Turing Machine）是图灵在 1936 年发表的 "On Computable Numbers, with an Application to the Entscheidungsproblem"（《论可计算数及其在判定性问题上的应用》）中提出的
数学模型
既然是数学模型，它就并非一个实体概念，而是架空的一个想法。在文章中图灵描述了它是什么，并且证明了， 只要图灵机可以被实现，就可以用来解决任何可计算问题 。
图灵机结构
图灵机的结构包括以下几个部分：
- 一条无限长的纸带（tape），纸带被分成一个个相邻的格子（square），每个格子都可以写上至多一个字符（symbol）。
- 一个字符表（alphabet），即字符的集合，它包含纸带上可能出现的所有字符。其中包含一个特殊的
空白字符（blank），意思是此格子没有任何字符。 - 一个读写头（head），可理解为指向其中一个格子的指针。它可以读取/擦除/写入当前格子的内容，此外也可以每次向左/右移动一个格子。
- 一个状态寄存器（state register），它追踪着每一步运算过程中，整个机器所处的状态（运行/终止）。当这个状态从运行变为终止，则运算结束，机器停机并交回控制权。如果你了解
有限状态机，它便对应着有限状态机里的状态。 - 一个有限的指令集（instructions table），它记录着读写头在特定情况下应该执行的行为。可以想象读写头随身有一本操作指南，里面记录着很多条类似于 " 当你身处编号 53 的格子并看到其内容为 0 时，擦除，改写为 1，并向右移一格。此外，令下一状态为运行。" 这样的命令。其实某种意义上，这个指令集就对应着程序员所写下的程序了。
在计算开始前，纸带可以是完全空白，也可以在某些格子里预先就有写上部分字符作为输入。运算开始时，读写头从某一位置开始，严格按照此刻的配置（configuration），即：
- 当前所处位置
- 当前格子内容
来一步步的对照着指令集去进行操作，直到状态变为停止，运算结束。而后纸带上留下的信息，即字符的序列（比如类似 "...011001..."）便作为输出，由人来解码为 自然语言。
要重申一下，以上只是图灵机模型的内容，而非具体的实现。所谓的纸带和读写头都只是图灵提出的 抽象概念
为便于理解打一个比方
抽象比喻
算盘虽然不是图灵机（因为它没有无限长的纸带，即无限的存储空间），但它的行为与图灵机一致。每一串算珠都是纸带上的一格，一串算珠上展示的数字便记录着当前格中的字符（可以是空白，可以是 12345 ）
人类的手即是读写头，可以更改每串算珠的状态。算盘的运行遵循人脑中的算法，当算法结束，算盘停机
图灵机可以解决什么问题
假设 上述模型里所说的功能都能被以某种形式物理实现， 那么 任意可计算问题都可以被解决
在计算机领域，或者说自动机领域，我们研究的一切问题都是计算问题（Computational Problem）。它泛指一切与计算相关的问题。
计算问题的一些举例：
- 给定一个正整数 n，判断它是否是质数
- 给定一个 01 序列，把它们按位取反
非计算问题的例子：
- 今晚吃什么
- 为什么太阳从东边升起
计算问题有的可以解决，有的不可解决。这就引出了计算问题的可计算性（Computability）
如上面的问题 1，我们当然可以找到一个算法来解决判断任意正整数 n 是否为质数的问题（比如从 2 遍历到 n-1，看 n 是否可以整除它）
所以，问题 1 就是可计算的。
也有一些不可计算的计算问题，比如著名的 停机问题（Halting Problem)
Halting Problem: given the description of an arbitrary program and a finite input, decide whether the program finishes running or will run forever.
它的表述是这样的：给定一段程序的描述和该程序的一个有效输入，运行此程序，那么程序最终是会终止，还是会死循环下去？
它是一个不可判定问题（Undecidable Problem）。即不存在一个 **通用** 算法，可以在任意输入下解决此问题
图灵在文章里很优雅的用反证法推翻了假设“假设有这么一个算法可以解决任何停机问题”，从而证明了这样的算法并不存在什么是图灵完备
图灵完备性（Turing Completeness）是针对一套数据操作规则而言的概念。
数据操作规则可以是一门编程语言，也可以是计算机里具体实现了的指令集。
当这套规则可以实现图灵机模型里的全部功能时，就称它具有图灵完备性
常见不完备原因
图灵不完备的语言常见原因有循环或递归受限 (无法写不终止的程序,如 while(true){}; ), 无法实现类似数组或列表这样的数据结构 (不能模拟纸带). 这会使能写的程序有限
缺点
图灵完备可能带来坏处, 如 C++ 的模板语言, 模板语言是在类型检查时执行, 如果编译器不加以检查,我们完全可以写出使得 C++ 编译器陷入死循环的程序.
图灵不完备也不是没有意义, 有些场景我们需要限制语言本身. 如限制循环和递归, 可以保证该语言能写的程序一定是终止的.
直观理解图灵完备——Brainfuck 语言
如今主流的编程语言（C++，Java，Python，以及等等等等）都是图灵完备的语言
关于语言优劣之争也只是在其封装、优化等方面，以及因为这些区别而产生的 " 不同语言适用于不同情况 " 的争执。如果我们回到最底层，就会发现它们可以实现的功能其实完全一样，并且本质上就是一个图灵机
在 1993 年，Urban Müller 发明了 Brainfuck 语言。这门语言可以说是编程语言界的 helloworld 了——它一共只含有 8 个有效字符，每个有效字符就是一条指令
语言虽然极致轻量，它却是一门图灵完备的编程语言
Brainfuck is fully Turing-complete.
一门新语言功能语法很复杂，要用数学证明的方式确定性说明它图灵完备会很麻烦，但只要用这门新语言实现一个 brainfuck 的解释器，那么就必然证明了是图灵完备的
示例
先贴上一段 BF 的代码，体验一下它的画风：
++++++++ [ > ++++ [ > ++ > +++ > +++ > + <<<< - ] > + > + > - >> + [ < ] < - ] >>. > ---. +++++++.. +++. >>. < -. <. +++. ------. --------. >> +. > ++.这个程序编译运行后，控制台打印 "Hello World!"。
BF 的工作机制与图灵机高度一致。首先它存储数据的方式是一个不限长的一维整数数组，里面的数值全部初始化为 0。此外，有一数据指针，每一时刻都指向数组的某一任意元素。指针可以向左/右移动，也可以读取/修改当前值。
语言里的 8 个有效字符分别是：
> 指针向右移动一格
< 指针向左移动一格
+ 使指针当前格数值加一
- 使指针当前格数值减一
. 把当前格数值按 ASCII 表输出到终端
, 从终端接受一 byte 的数据，存储其 ASCII 数值到当前格
[ 当指针当前值为 0 时，程序跳转至与之对应的 ] 之后；否则程序正常执行
] 程序跳转回与之对应的 [ 处有了这些工具，我们可以很快做出一个计算乘法的程序。因为 ASCII 表中 'A' 对应的值为 65，可以使用 5 * 13 算出 65 并输出得到字符 'A'。
+++++
[
> +++++++++++++
< -
]
>.解释：
- 把指针初始处的格子命名为 cell 0，cell 0 右边的那个格子命名为 cell 1。那么第一句将其递增 5 次变为 5。
- 循环执行 " 右移指针，递增 13 次， 左移指针，递减 1 次 "。当 cell 0 的值最终被递减为 0 的时候，循环结束。
- 此时 cell 1 的值执行了 5 次 " 递增 13 次 " 的操作，即 65。指针右移至 cell 1，输出此格子，则在终端会看到 'A'。
gif 示例
Brainfuck Visualizer - FreddieRa - OpenProcessing
参考
贡献者
jiechen