关于图灵完备

什么是图灵机

图灵机（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 的代码，体验一下它的画风：

1	++++++++ [ > ++++ [ > ++ > +++ > +++ > + <<<< - ] > + > + > - >> + [ < ] < - ] >>. > ---. +++++++.. +++. >>. < -. <. +++. ------. --------. >> +. > ++.

这个程序编译运行后，控制台打印 “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