你可能永远都搞不懂了图灵机了！

‍（给程序员零距离加星标，了解项目开发.）

程序员都知道图灵机，但是却不一定能搞懂它，不一定理解它为什么这么厉害。

原因就是：图灵机太简单了，太数学了， 太抽象了。 

1

我刚上大学的时候，有个社团叫“图灵学社”，当时我还纳闷，图灵是谁？

我就跑到图书馆去查书：哇，图灵原来是我们的祖师爷啊，我们全靠他赏饭吃。 

等等，这图灵机是什么玩意儿，一条纸带，一个读写头，一个控制器， 这也太简单了吧。

现在的电脑有漂亮的界面，丰富的操作，有视频，图片，声音。 

编程中有虚拟机，各种框架，并发模型，设计模式，面向对象，泛型，函数式，闭包。

这么复杂的东西，怎么可能归结到如此简单的图灵机中？这不是痴心妄想吗？

2

这还真不是痴心妄想。因为计算机使用的二进制数字可以表示一切！

先说图像。

图像有两种存储方式，一种是位图，一种是矢量图。

位图相当于把整个图像分解成一个个小的像素，每个像素都有颜色，这样就可以用二进制数字表达了。

就像下面这张笑脸图：

（可以看出图像放大以后就出现锯齿了。）

而矢量图相当于记录下了一个图像的几何信息。

比如一个圆，只要知道

1. 圆心

2. 半径

3. 绘制时的线型和颜色

就可以把他复原了， 很明显，这些数据也可以用二进制表示。

视频则是一帧帧的图像组成，既然图像可以用二进制表示，那视频肯定也没问题。

声音也是类似的，本来是连续的，但是电脑会对他进行采样（比如每秒采样44100次），变成离散的，就可以用二进制表达，存放到电脑中了。

（音频信号也出现锯齿了，因为数据是离散的，不是连续的了，不过只要采样频率高，人的耳朵分辨不出来）

所以，视频，图像，文本，声音都可以用二进制来表达，然后写程序对他们进行处理就行了。 

至于各种语言编写的程序，无论是系统级的操作系统，还是应用层的Web网站， 最终都要归结到赋值，顺序，循环，分支这些最基本的结构。

如果你不相信，可以看看我之前写过几篇的文章：

《编程语言的巅峰》

《C语言哭了，过年回家，只有我没有对象》

《这世界上根本没什么面向对象》

所以只要图灵机能表达这些最基本的结构，一切问题就都解决了。 

3

本文的重点终于来了， 图灵机如何去表达这些基本的结构呢？

进入烧脑环节，强烈建议找一块儿安静的时间来阅读。  

（其实做为一个程序员，多用脑子是好事，不要一遇到难点儿的东西就逃了，那样怎么会进步和成长呢？）

我们先从一个极其简单的编程语言来热身， 这个语言只有三条指令

1. 递增   

incr(X)

2. 递减

decr(X)

3. 循环

while(X){

    decr(X)

    //做一些事情

}

别小看这三条指令，从它们出发，可以组合出很多新的指令，可以把这些指令称为宏。 

这些宏一旦建立，可以再次被组合使用

第一个宏：   把一个变量X的值清0，记做 X <--0

while(X){

    decr(X)

}

第二个宏：  给一个变量赋值，记做 X <-- n

X <-- 0  //复用第一个宏

incr(X)

incr(X)

incr(X)

.....

incr(X)   //重复n次，不要嫌啰嗦，计算机最适合，最擅长干这种重复的事情

第三个宏：把X的赋值给Y ，记做 Y <--X

Y <--0    //利用第二个宏

while(X){

    decr(X)

    incr(Y)

}

第四个宏：实现if 语句  ，记做 if X then A

//注意，X的值只能是0或者1

while(X){

    decr(X)

    A 

}

实际上，只要你愿意，还可以组合出各种各样的新指令

Y <--- Y + X  

Y <--- Y * X

......

只不过需要花费更多的指令罢了。 

也就是说这个简单的语言能实现上一节所说的赋值，顺序，循环，分支等基本结构。 

那如果图灵机和这个简单语言也是等价的，那图灵机肯定能实现赋值，顺序，循环，分支了，对吧？ 

4

接下来我们把目光转向一个“寒酸”的图灵机， 让它来实现decr(X), incr(X), while(X)

这个图灵机的磁带上只有空白（b）和字符 (1)两种选择

两个空白之间有多少个1就表示数字是多少，例如有4个1表示4， 10个1表示 10

下图就表示数字7

就是这么简单粗暴！

磁带上的读写头总是指向磁带上的一个符号（当前符号），读写完成以后，它可以左移，右移或者呆那儿不动， 这依赖于控制器中的指令是什么样子的。

最重要的是那个控制器，相当于现代的CPU了，它是一个有限状态的自动机，可以在有限的状态中根据输入转入另外一个状态。 

我们现在试试用这个“寒酸”的图灵机来实现dec(X) ：对X加 1 。 

为了方便说明，假设X为7， 读写头初始状态位于最左端的空白处

是不是很简单？ 

当然，这里可以用有限状态机来描述，为了降低理解负担， 我用大白话来说了。

想实现decr (X) ，就更简单了， 我们把刚才的X=8，减去1

首先让读写头右移，遇到1，把它变成b ，停止就行。

循环要稍微复杂一点儿，仔细看好了。 

假设X = 3，循环是这样的

while(X){

     循环体

}

三种基本的运算实现了，现在我们可以说：

简单图灵机 <--> 简单语言 <-->  复杂的语言

好了，证明完毕！不知道你晕了没有。

其实这根本不是证明，就是希望大家能感受下图灵这么简单的机器，也有着强悍的能力，就是实现起来比较费劲罢了。 

后记：本文的简单语言和图灵机的例子来源于佛罗赞的《计算机科学导论》，这本书相当不错，推荐！

- END -

文章精选1、当特斯拉遇到CPU,会发生什么？2、免翻！可看油管视频，号称国内YouTube！3、提醒！恢复出厂不靠谱，旧手机仍有“记忆”！4、182.28亿！阿里遭遇中国史上最大额罚款5、一粒米？最小电脑竟然那么小？6、哈哈哈哈，这个勒索软件笑死我了！7、大佬推荐！收藏绝不后悔的开源软件！
8、HTTP也恋爱了！你呢？

更多精彩等待你的发现点分享点点赞点在看