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

軟萌可愛的貓咪，總會喚起我們想要「擼貓」或者「吸貓」的沖動。

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

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

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

測試對象就是這只小貓Peluche

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

什么是圖靈完備?

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

也就是說，任何能夠通過以下4項測試的機(jī)器都是一臺計算機(jī)（因此可以執(zhí)行任何類型的計算）。 這4項測試是：

.和, —— 輸入和輸出一個值。

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

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

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

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

圖靈完備性的證明

輸入輸出

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

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

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

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

增減內(nèi)存值

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

到處都是貓糧……

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

「貓貓計算機(jī)」似乎是一個新手會犯的錯誤，但即使是最有經(jīng)驗的開發(fā)人員，有時也會犯新手錯誤，承認(rèn)這一點沒什么難為情的。

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

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

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

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

參考資料：

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

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

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

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