猫=图灵机？4项测试证明，「猫猫计算机」可执行任意计算

【导读】近日，一位法国开发者Chloé Lourseyre在她的个人博客上提出了「猫猫计算机」的概念。由此，她提出了一个天马行空的想法：猫是不是「图灵完备」的？它是「图灵机」吗？

软萌可爱的猫咪，总会唤起我们想要「撸猫」或者「吸猫」的冲动。 

和猫咪待在一块，还真有种治愈的感觉。 

而且，按照一位法国开发者Chloé Lourseyre的说法，猫咪甚至可以当计算机用！ 

近日，在她的个人博客上讨论了一个很重要的话题：猫是不是「图灵完备」的？它是「图灵机」吗？ 

 测试对象就是这只小猫Peluche 

Peluche是一只毛茸茸的小猫，就住在Chloé Lourseyre家里。它就是今天的测试对象。 

什么是图灵完备?

图灵完备性的概念是，如果某台设备可以模拟图灵机，那么它就可以执行任何类型的计算。 

也就是说，任何能够通过以下4项测试的机器都是一台计算机（因此可以执行任何类型的计算）。 这4项测试是：

.和, —— 输入和输出一个值。

+ 和 - —— 增加和减少当前存储单元中包含的值。（图灵机有一个「存储带」，上面有「存储单元」。机器总是指向一个存储单元，也就是上面提到的「当前」存储单元。）

> 和 < —— 向左或向右移动当前存储单元。

[和] —— 执行循环。 

所以，如果 Peluche 能够通过这4项测试，就可以认为它是「图灵完备」的。 

图灵完备性的证明

输入输出

首先，为了验证能不能得到反馈，Chloé Lourseyre用手戳了戳 Peluche。 

它看了Chloé Lourseyre一眼，然后才转过身。 

所以是这样的：Chloé Lourseyre戳了它一下，然后得到了一个反应。结论很明确，Peluche可以处理输入，并给出输出。 

输入、输出已确认！ 

增减内存值

前几天，Chloé Lourseyre下班回来，发现厨房变成了这样： 

到处都是猫粮…… 

但后来Chloé Lourseyre仔细观察了一下，发现可以把撒上猫粮的地板按位置进行编号，就像下面这样： 

在Chloé Lourseyre看来，这看起来很像内存带！Peluche可以将猫粮洒在地砖上，然后直接在地砖上吃掉它们，因此，Peluche可以增加和减少给定存储单元中包含的值。 

增减内存值，已确认！ 

左右移动当前内存单元

还有一次，Chloé Lourseyre在洗碗时不小心把一些水洒在了 Peluche 身上。它开始在厨房里到处乱跑，弄得一团糟。 

但是如果仔细观察（在红色箭头的尖端），不难注意到，Peluche一边乱跑，一边把自己装食物的碗移动了位置。 

也就是说，Peluche将它的食物洒到另一块瓷砖上。这相当于移动指向当前内存的指针，编辑另一个内存单元。 

移动内存单元，已确认！ 

执行循环

在厨房被Peluche搞的一团乱之后，很明显，Chloé Lourseyre不得不清理打扫。 

然后不到五分钟后，Chloé Lourseyre回到厨房，又变成这样了： 

所以，Peluche绝对可以执行循环...... 

循环已确认！ 

到这里为止，Chloé Lourseyre已经证明了Peluche确实是「图灵完备」的。那么下一个问题是，如何使用Peluche来执行高性能计算任务？ 

如何执行？首先要有代码，Chloé Lourseyre编了一段简单的代码，就像下面这样：（这个代码示例是一种奇特的新语言，名为「braincat」） 

结果：Peluche什么都不做！

所以最后，Chloé Lourseyre不禁想，虽然猫是「图灵完备」的，但可能不是为了执行代码而设计的？ 

关于「猫猫计算机」

上面的「猫猫计算机」当然都是说笑话。 根据Chloé Lourseyre的经验，当有人发现一种语言的新特征时，就开始到处使用。 

「猫猫计算机」似乎是一个新手会犯的错误，但即使是最有经验的开发人员，有时也会犯新手错误，承认这一点没什么难为情的。 

实际上，在面对编程语言的全新版本中的新功能时，积累经验的最好办法，就是把每个功能错误地使用一次，以避免今后的误用。 

在使用某项功能之前，一定要先问问自己，这样做实际上是否有必要，否则你也可能犯下像「猫猫计算机」这样的错误。 

另外，猫猫计算机很费猫，所以不要这样做。 

(此文的写作过程中，没有猫猫受到伤害，但有一只猫被轻轻地戳过几下。) 

参考资料：

https://belaycpp.com/2021/11/24/is-my-cat-turing-complete/ 

https://en.wikipedia.org/wiki/Turing_completeness 

本文来自微信公众号“新智元”（ID:AI_era），编辑：David 小咸鱼，36氪经授权发布。

相关推荐

计算机不是只会“计算”，图灵机也不是一台“机器”
哥德尔90年前的「不完备性定理」，奠定了计算机与AI的理论基础
用跑得最慢的电脑程序，理解最高深的哥德巴赫猜想
图灵奖公布，计算机图形学先驱Hanrahan和Catmull获奖，二人见证了好莱坞3D动画电影史
最前线｜618到了，你的购物车里装着几级猫猫？
人工智能新突破：计算机正在学习从更高维度观察世界
量子计算：疯狂赛道上四大巨头如何应战
IBM直怼谷歌“实现量子霸权”：1万年太久，经典计算机只需2天半
AI计算“大练兵”成绩出炉：谷歌、英伟达、浪潮分获各任务最好成绩
第一代智能宠物饮水机两周众筹超 2 万台,「猫猫狗狗」想用高性价比产品抓住“品类机会”

网址: 猫=图灵机？4项测试证明，「猫猫计算机」可执行任意计算 http://www.xishuta.com/newsview55326.html