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

川长思鸟来 2023-01-13 04:29 215阅读 0赞

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

![c25c2e240ea135989144ddec035e1127.png][]

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

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

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

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

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

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

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

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

先说**图像**。

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

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

就像下面这张笑脸图：

![9d231e648b49b6ea4165993e22477503.png][]

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

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

比如一个圆，只要知道

1. 圆心

2. 半径

3. 绘制时的线型和颜色

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

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

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

![694afeeb1b2fe74d47c153563eba275d.png][]

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

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

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

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

《[编程语言的巅峰][Link 1]》

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

《[这世界上根本没什么面向对象][Link 2]》

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

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

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

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

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

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)   //重复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)

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

Y <--- Y + X

Y <--- Y \* X

......

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

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

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

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

![becb2a96ee111689243f4c80a6f0a417.png][]

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

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

下图就表示数字7

![733b995bd6623b6bb399198a8782a609.png][]

就是这么简单粗暴！

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

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

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

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

![c6b9eddeaa85f109e81d95a57687f797.gif][]

是不是很简单？

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

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

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

![5b987162406c98221818079345453233.gif][]

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

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

while(X)\{

循环体

![fc80c4397f31890e24d7df004ba1b7f8.gif][]

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

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

好了，证明完毕！不知道你晕了没有。![46537a8a5b1a1eda5b6df80cbe5c88a2.png][]

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

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

![73bd1c80a61aed4b27be379699af4352.gif][]

[码农翻身3年精华文章（必读！）][3]

[漫画丨让你专心干技术，没让你干到35岁啊…][35]

[漫画 | Linux之父：我财务自由以后，失眠了][_ Linux]

[漫画：打死我也不搞负载均衡了][Link 3]！

[漫画：兄弟，今晚又得熬个通宵了！][Link 4]

[架构师劝退指南][Link 5]

[程序员的宿命][Link 6]

[宇宙第一IDE到底是谁？][IDE]

[HTTP Server ：一个差生的逆袭][HTTP Server]

[如何降低程序员的工资？][Link 7]

[程序员，你得选准跑路的时间！][Link 8]

[Javascript: 一个屌丝的逆袭][Javascript_]

[我是一个线程][Link 9]

[TCP/IP之大明邮差][TCP_IP]

[一个故事讲完Https][Https]

[CPU 阿甘][CPU]

[c25c2e240ea135989144ddec035e1127.png]: /images/20221022/574fd5ee47e145a787b2352d771ccc60.png
[9d231e648b49b6ea4165993e22477503.png]: /images/20221022/626a06e86fbe41639f19391282097836.png
[694afeeb1b2fe74d47c153563eba275d.png]: /images/20221022/c9e9fb00fbba45aab3b86898a16229d0.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzAxOTc0NzExNg%3D%3D&chksm=80d66f24b7a1e6326ce99d8624f25219e85f0863743e3bebacd72f0b29601a615145ae3fdd46&idx=1&mid=2665518951&scene=21&sn=3ade06788dd91da6d955390098eef942#wechat_redirect
[C]: http://mp.weixin.qq.com/s?__biz=MzAxOTc0NzExNg%3D%3D&chksm=80d65585b7a1dc93034e2ece36becc6fef6ca30df6c32a5ae439642011cbc1b85ca277bc58f0&idx=1&mid=2665524678&scene=21&sn=ff4a0dd17f4639514b8122c8f915de1d#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzAxOTc0NzExNg%3D%3D&chksm=80d669b8b7a1e0aebaf9b11ed6bb90541d96334c7516fd4bb019442dbec22e18a330152aaaf4&idx=1&mid=2665517563&scene=21&sn=e2d785a8a8b39c557125af95d0b3ae08#wechat_redirect
[becb2a96ee111689243f4c80a6f0a417.png]: /images/20221022/3a5278f1deeb4064af86f7439d15312f.png
[733b995bd6623b6bb399198a8782a609.png]: /images/20221022/ef540db481594f7cbd4c01331ad4df8f.png
[c6b9eddeaa85f109e81d95a57687f797.gif]: /images/20221022/bec857e617fa44198915a98a7bc4599b.png
[5b987162406c98221818079345453233.gif]: /images/20221022/11d4490d518b465d876de39dd92b397e.png
[fc80c4397f31890e24d7df004ba1b7f8.gif]: /images/20221022/91227db6d17d47edb7a21c4758f19600.png
[46537a8a5b1a1eda5b6df80cbe5c88a2.png]: /images/20221022/81dd336ee3274220a6e9b3e042fd2633.png
[73bd1c80a61aed4b27be379699af4352.gif]: /images/20221022/3a32581753ac4cb79925906b26d4569e.png
[3]: http://mp.weixin.qq.com/s?__biz=MzAxOTc0NzExNg%3D%3D&chksm=80d651cdb7a1d8db44237fec1fc2410da047ba639ba7e39edce3bbcdee28014718e6c6227b09&idx=1&mid=2665523598&scene=21&sn=ecb7512a1b1dbab5620d78c4963b5627#wechat_redirect
[35]: http://mp.weixin.qq.com/s?__biz=MzAxOTc0NzExNg%3D%3D&chksm=80d65775b7a1de6306afc07c2218c22dea56719198d488d94ad6f6db0501dfb139ea8d6f7d37&idx=1&mid=2665525046&scene=21&sn=917301d473491e81a2cea2166bac084b#wechat_redirect
[_ Linux]: http://mp.weixin.qq.com/s?__biz=MzAxOTc0NzExNg%3D%3D&chksm=80d656b1b7a1dfa7aff4b1cb177913cb108d8eadc0854c45a1be1a68926562ad4a9b5b2fc450&idx=1&mid=2665524978&scene=21&sn=5b65197d219d70062a2a5f72ebc3f4a2#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzAxOTc0NzExNg%3D%3D&chksm=80d655b9b7a1dcaf29fb8d2e0b2d87ee10a5f2c2f1ca8e591b664c1cbce4a873cab1d1838c57&idx=1&mid=2665524730&scene=21&sn=9f55452be926dcef67d362f53a9a5e6d#wechat_redirect
[Link 4]: http://mp.weixin.qq.com/s?__biz=MzAxOTc0NzExNg%3D%3D&chksm=80d65927b7a1d031ec5e747627b86540056ed82006c300e2c8484b411447baf92d58ad8b6a82&idx=1&mid=2665521508&scene=21&sn=137269f8b286f3d9191be0ce9d6fdb1c#wechat_redirect
[Link 5]: http://mp.weixin.qq.com/s?__biz=MzAxOTc0NzExNg%3D%3D&chksm=80d667bbb7a1eeadb33b011a2fee71a4eb25635ebed0f4011f7c2b84b6103f18cd6633c299a8&idx=1&mid=2665521144&scene=21&sn=f7c7fd0ac7a26a22b64671a7f67faa8d#wechat_redirect
[Link 6]: http://mp.weixin.qq.com/s?__biz=MzAxOTc0NzExNg%3D%3D&chksm=80d66529b7a1ec3f9e266072ff2d4839df4082fa702d84be76e51d15326b34b7034278ce7ee4&idx=1&mid=2665520490&scene=21&sn=6dd71186fd2d648c29d69f541a8c7baf#wechat_redirect
[IDE]: http://mp.weixin.qq.com/s?__biz=MzAxOTc0NzExNg%3D%3D&chksm=80d661b1b7a1e8a70568d243a20c210eaf474650efc61e809dcf8e5d534be1d7f15ce1145295&idx=1&mid=2665519602&scene=21&sn=f85e22d32d4919116afbb2808f1a151a#wechat_redirect
[HTTP Server]: http://mp.weixin.qq.com/s?__biz=MzAxOTc0NzExNg%3D%3D&chksm=80d661efb7a1e8f9981903e2d7f0754449769973c80e5c7539930e89d7a3ffe0bdd74aabd8d5&idx=1&mid=2665519532&scene=21&sn=d17efeb01b6114fe20ea60d08c7836b2#wechat_redirect
[Link 7]: http://mp.weixin.qq.com/s?__biz=MzAxOTc0NzExNg%3D%3D&chksm=80d66df9b7a1e4ef28922b2241a998efd59cfc8d1693fe41b84d6ea31935d38feae2af68164a&idx=1&mid=2665518522&scene=21&sn=b1814b820074777a25281975df622e1c#wechat_redirect
[Link 8]: http://mp.weixin.qq.com/s?__biz=MzAxOTc0NzExNg%3D%3D&chksm=80d66eb1b7a1e7a72165940271001720e7853da6d324e6d9a0055b4a8c636d4bdbb7c1f1bfb9&idx=1&mid=2665518834&scene=21&sn=5dcedf3fc7e318f50cd32fffe38c429d#wechat_redirect
[Javascript_]: http://mp.weixin.qq.com/s?__biz=MzAxOTc0NzExNg%3D%3D&chksm=80d67820b7a1f136d73b874e5784f06ef34eb38d7750712a5b9c7532ad44f18a3d43d2edbfbd&idx=1&mid=2665513059&scene=21&sn=a2eaf97d9e3000d15a33681d1b720463#wechat_redirect
[Link 9]: http://mp.weixin.qq.com/s?__biz=MzAxOTc0NzExNg%3D%3D&chksm=06ef67ee3198eef85a668f7197709b54bcd9508087ace8f6eaa11d34eb4e5392c5190a77d530&idx=1&mid=416915373&scene=21&sn=f80a13b099237534a3ef777d511d831a#wechat_redirect
[TCP_IP]: http://mp.weixin.qq.com/s?__biz=MzAxOTc0NzExNg%3D%3D&chksm=80d678c5b7a1f1d3e122ae99f368671acb7f6baecebb6488c8ca63caa7f1ef28fea1a4dc1ef0&idx=1&mid=2665513094&scene=21&sn=a2accfc41107ac08d74ec3317995955e#wechat_redirect
[Https]: http://mp.weixin.qq.com/s?__biz=MzAxOTc0NzExNg%3D%3D&chksm=80d67b70b7a1f26697fa1626b3e9830dbdf4857d7a9528d22662f2e43af149265c4fd1b60024&idx=1&mid=2665513779&scene=21&sn=a1de58690ad4f95111e013254a026ca2#wechat_redirect
[CPU]: http://mp.weixin.qq.com/s?__biz=MzAxOTc0NzExNg%3D%3D&idx=1&mid=2665513017&scene=21&sn=5550ee714abd36d0b580713f673e670b#wechat_redirect