你無意中發現過哪些圖靈完全的系統？

01-25

Wireworld是著名的元胞自動機之一，當然也不是我親自發現的，是由著名計算機科學家Brian Silverman在1987年提出的。它和其他元胞自動機具有類似的規則，也就是每幀每格的新狀態由之前該格及其鄰近的格子決定。
Wireworld中格子的四種可能狀態：
- 空（黑）：始終為空。
- 電子頭（藍）：下一幀變為電子尾。
- 電子尾（紅）：下一幀變為導線。
- 導線（黃）：如果附近8格有一個或兩個電子頭，則在下一幀變為電子頭，否則維持導線。

（動圖可以在英文維基上看到: https://en.m.wikipedia.org/wiki/Wireworld）

上圖為wireworld二極體。

根據上述規則，一個電子頭和一個電子尾組成的「電子信號」可以在一根呈直線的導線中單向傳播，並和另一個電子信號迎頭相撞時「湮滅」。不僅如此，電子信號在遇到較為複雜的連接點時也會展現出不同的特性，如上述的二極體可以做到只允許信號從一邊通過而阻止另一邊過來的信號。

在wireworld中，你可以只憑導線和一個或多個初始的電子信號製作出邏輯門，頻率放大器，只讀內存，觸發器，鎖存器等等基本電子元件。具體的實例示範可以參考下述網站：
http://karlscherer.com/Wireworld.html

上圖為信號發生器和異或門（XOR）。

上圖為ROM，注意每個單元格有個針腳不同來決定信號是否通過。

只要你對計算機原理有足夠的了解，在2D的wireworld里完全就能做出計算機來。而且wireworld的規則及其簡潔，編寫難度低，具有強烈的電路感，是圖靈完備系統中非常美觀的存在。

其他類似的圖靈完備的元胞自動機還有蘭頓螞蟻等，有興趣的可以研究一下。

至於我是怎麼發現的。。。

你們知道有個手游叫the sandbox嗎？（一度是我除了圍棋以外唯一玩的手游）。它採用了wireworld規則來設計電路，不過遊戲本身其實也是複雜元胞自動機的概念（包括落沙，水流處理等），是真正的「沙盒」遊戲。評論里還提到了The Powder Toy，也是「沙盒」遊戲非常好的示範。

等我學會了GPU編程，好想自己寫一個巨大無比的sandbox來玩玩啊。

額，都不是我想出來的，不過還是很有趣&> &<

圖片來自wiki(Turing completeness)

掃雷是圖靈完備的
萬智牌是圖靈完備的
超級馬里奧也是圖靈完備的
還記不記得有個零玩家的生命演化遊戲，那也是圖靈完備的

友情鏈接

證明掃雷是圖靈完備的 http://web.mat.bham.ac.uk/R.W.Kaye/minesw/infmsw.pdf
Magic: The Gathering is Turing complete
Accidentally Turing-Complet

多米諾骨牌算嗎？

用10000塊多米諾骨牌搭建的計算機。http://www.bilibili.com/video/av12615781

必須是 Human Resource Machine (人力資源機器), 這個遊戲用 11 個指令讓你能夠完成一切. 類似的還有 Sequence 和 http://Shenzhen.io

C++模板

紅警啊...

還記得三體里的秦始皇嗎...

造一隊美國大兵...

美國大兵有站起和蹲下兩種狀態...

然後和相鄰的美國大兵聯動起來就變成了............呃........元胞自動機.......

獲得圖靈機*1

============================

本來想答MC紅石或者撿垃圾4的...然後突然想到了人肉計算機........

看到上面@Trek 的回答中提到x86的MMU之後，想到x86的mov指令也被證明為圖靈完全了，雖然不是我自己發現的，不過也可以拿來說說。

證明地址:http://www.cl.cam.ac.uk/%7Esd601/papers/mov.pdf

mov是x86彙編中最基礎的一個，功能是移動數據，比如把一個寄存器中的數據放入另一個寄存器、把一個寄存器中的數據放入內存、把一個新的數字放入寄存器等操作。但因為其支持變址定址數據等具有控制型的操作，使其可以單指令圖靈完全。

其實mov不僅僅可以模擬圖靈機，它甚至可以較簡單的模擬其他大部分x86指令(當然不包括那些無可替代的，如:hlt/rdtsc等)。git上看到過一個項目，就是用這個原理可以把任意c程序編譯為幾乎只有mov指令的二進位文件並正常運行。

項目地址:xoreaxeaxeax/movfuscator

引用項目git頁面上的兩張圖，這是同一個求質數的主程序，正常編譯和使用這個項目之後。

至於具體的實現，當初簡單閱讀了下源代碼，舉兩個例子，運算和分支他大概是這樣實現的，不過時間比較長了，而且我也沒仔細看，只能說個大概。

運算的話，你可以事先在程序內存里放一個九九乘法表一樣的二維數組，他的兩個維度作為乘數，目標成員是結果，你就可以使用類似mov 結果,[乘數1+乘數2*列數]這樣的指令來進行乘法運算。多位數乘法的話只需要多次暫存和一些中間運算。同理，各種其他數學和邏輯運算都可以實現。

至於分支，如果你想實現當某個輸入值為0和1時分別得到另外兩個不同的值a和b，你只需要在內存里設置一個結構，其中偏移量為0的地方是a，為1的地方為b，然後以這個輸入值為指針的偏移量來mov就行了。

x86 CPU的內存管理單元，也就是MMU，被證明是圖靈完全的。

不知道細胞是不是（生物意義上的）

https://arxiv.org/pdf/1702.08889.pdf

我的Minecraft呢

1. sed

Implementation of a Turing Machine as Sed Script

Turing.sed

2. TeX

"Lists in TeX"s Mouths"