【導(dǎo)讀】近日，一位法國(guó)開(kāi)發(fā)者Chloé Lourseyre在她的個(gè)人博客上提出了「貓貓計(jì)算機(jī)」的概念。由此，她提出了一個(gè)天馬行空的想法：貓是不是「圖靈完備」的？它是「圖靈機(jī)」嗎？

軟萌可愛(ài)的貓咪，總會(huì)喚起我們想要「擼貓」或者「吸貓」的沖動(dòng)。

和貓咪待在一塊，還真有種治愈的感覺(jué)。

而且，按照一位法國(guó)開(kāi)發(fā)者Chloé Lourseyre的說(shuō)法，貓咪甚至可以當(dāng)計(jì)算機(jī)用！

近日，在她的個(gè)人博客上討論了一個(gè)很重要的話題：貓是不是「圖靈完備」的？它是「圖靈機(jī)」嗎？

測(cè)試對(duì)象就是這只小貓Peluche

Peluche是一只毛茸茸的小貓，就住在Chloé Lourseyre家里。它就是今天的測(cè)試對(duì)象。

什么是圖靈完備?

圖靈完備性的概念是，如果某臺(tái)設(shè)備可以模擬圖靈機(jī)，那么它就可以執(zhí)行任何類型的計(jì)算。

也就是說(shuō)，任何能夠通過(guò)以下4項(xiàng)測(cè)試的機(jī)器都是一臺(tái)計(jì)算機(jī)（因此可以執(zhí)行任何類型的計(jì)算）。 這4項(xiàng)測(cè)試是：

.和, —— 輸入和輸出一個(gè)值。

+ 和 - —— 增加和減少當(dāng)前存儲(chǔ)單元中包含的值。（圖靈機(jī)有一個(gè)「存儲(chǔ)帶」，上面有「存儲(chǔ)單元」。機(jī)器總是指向一個(gè)存儲(chǔ)單元，也就是上面提到的「當(dāng)前」存儲(chǔ)單元。）

> 和 < —— 向左或向右移動(dòng)當(dāng)前存儲(chǔ)單元。

[和] —— 執(zhí)行循環(huán)。

所以，如果 Peluche 能夠通過(guò)這4項(xiàng)測(cè)試，就可以認(rèn)為它是「圖靈完備」的。

圖靈完備性的證明

輸入輸出

首先，為了驗(yàn)證能不能得到反饋，Chloé Lourseyre用手戳了戳 Peluche。

它看了Chloé Lourseyre一眼，然后才轉(zhuǎn)過(guò)身。

所以是這樣的：Chloé Lourseyre戳了它一下，然后得到了一個(gè)反應(yīng)。結(jié)論很明確，Peluche可以處理輸入，并給出輸出。

輸入、輸出已確認(rèn)！

增減內(nèi)存值

前幾天，Chloé Lourseyre下班回來(lái)，發(fā)現(xiàn)廚房變成了這樣：

到處都是貓糧……

但后來(lái)Chloé Lourseyre仔細(xì)觀察了一下，發(fā)現(xiàn)可以把撒上貓糧的地板按位置進(jìn)行編號(hào)，就像下面這樣：

在Chloé Lourseyre看來(lái)，這看起來(lái)很像內(nèi)存帶！Peluche可以將貓糧灑在地磚上，然后直接在地磚上吃掉它們，因此，Peluche可以增加和減少給定存儲(chǔ)單元中包含的值。

增減內(nèi)存值，已確認(rèn)！

左右移動(dòng)當(dāng)前內(nèi)存單元

還有一次，Chloé Lourseyre在洗碗時(shí)不小心把一些水灑在了 Peluche 身上。它開(kāi)始在廚房里到處亂跑，弄得一團(tuán)糟。

但是如果仔細(xì)觀察（在紅色箭頭的尖端），不難注意到，Peluche一邊亂跑，一邊把自己裝食物的碗移動(dòng)了位置。

也就是說(shuō)，Peluche將它的食物灑到另一塊瓷磚上。這相當(dāng)于移動(dòng)指向當(dāng)前內(nèi)存的指針，編輯另一個(gè)內(nèi)存單元。

移動(dòng)內(nèi)存單元，已確認(rèn)！

執(zhí)行循環(huán)

在廚房被Peluche搞的一團(tuán)亂之后，很明顯，Chloé Lourseyre不得不清理打掃。

然后不到五分鐘后，Chloé Lourseyre回到廚房，又變成這樣了：

所以，Peluche絕對(duì)可以執(zhí)行循環(huán)......

循環(huán)已確認(rèn)！

到這里為止，Chloé Lourseyre已經(jīng)證明了Peluche確實(shí)是「圖靈完備」的。那么下一個(gè)問(wèn)題是，如何使用Peluche來(lái)執(zhí)行高性能計(jì)算任務(wù)？

如何執(zhí)行？首先要有代碼，Chloé Lourseyre編了一段簡(jiǎn)單的代碼，就像下面這樣：（這個(gè)代碼示例是一種奇特的新語(yǔ)言，名為「braincat」）

結(jié)果：Peluche什么都不做！

所以最后，Chloé Lourseyre不禁想，雖然貓是「圖靈完備」的，但可能不是為了執(zhí)行代碼而設(shè)計(jì)的？

關(guān)于「貓貓計(jì)算機(jī)」

上面的「貓貓計(jì)算機(jī)」當(dāng)然都是說(shuō)笑話。 根據(jù)Chloé Lourseyre的經(jīng)驗(yàn)，當(dāng)有人發(fā)現(xiàn)一種語(yǔ)言的新特征時(shí)，就開(kāi)始到處使用。

「貓貓計(jì)算機(jī)」似乎是一個(gè)新手會(huì)犯的錯(cuò)誤，但即使是最有經(jīng)驗(yàn)的開(kāi)發(fā)人員，有時(shí)也會(huì)犯新手錯(cuò)誤，承認(rèn)這一點(diǎn)沒(méi)什么難為情的。

實(shí)際上，在面對(duì)編程語(yǔ)言的全新版本中的新功能時(shí)，積累經(jīng)驗(yàn)的最好辦法，就是把每個(gè)功能錯(cuò)誤地使用一次，以避免今后的誤用。

在使用某項(xiàng)功能之前，一定要先問(wèn)問(wèn)自己，這樣做實(shí)際上是否有必要，否則你也可能犯下像「貓貓計(jì)算機(jī)」這樣的錯(cuò)誤。

另外，貓貓計(jì)算機(jī)很費(fèi)貓，所以不要這樣做。

(此文的寫作過(guò)程中，沒(méi)有貓貓受到傷害，但有一只貓被輕輕地戳過(guò)幾下。)

參考資料：

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

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

本文來(lái)自微信公眾號(hào)“新智元”（ID:AI_era），編輯：David 小咸魚(yú)，36氪經(jīng)授權(quán)發(fā)布。

關(guān)鍵詞： 圖靈機(jī) 可執(zhí)行 計(jì)算機(jī)