你无意中发现过哪些图灵完全的系统？ 第1页

Wireworld是著名的元胞自动机之一，当然也不是我亲自发现的，是由著名计算机科学家Brian Silverman在1987年提出的。它和其他元胞自动机具有类似的规则，也就是每帧每格的新状态只由上一帧该格及其邻近的格子决定。

Wireworld中格子的四种可能状态：
- 空（黑）：始终为空。
- 电子头（蓝）：下一帧变为电子尾。
- 电子尾（红）：下一帧变为导线。
- 导线（黄）：如果附近8格有一个或两个电子头，则在下一帧变为电子头，否则维持导线。

根据上述规则，一个电子头和一个电子尾组成的“电子信号”可以在一根呈直线的导线中单向传播，并和另一个电子信号迎头相撞时“湮灭”。不仅如此，电子信号在遇到较为复杂的连接点时也会展现出不同的特性；如下图的二极管可以做到只允许信号从一边通过，而阻止另一边过来的信号。

在wireworld中，你可以只凭导线和一个或多个初始的电子信号制作出逻辑门，频率放大器，只读内存，触发器，锁存器等等基本电子元件。具体的实例示范可以参考下述网站：
http://karlscherer.com/Wireworld.html

只要你对计算机原理有足够的了解，在2D的wireworld里完全就能做出计算机来。而且wireworld的规则及其简洁，编写难度低，具有强烈的电路感，是图灵完备系统中非常美观的存在。

其他类似的图灵完备的元胞自动机还有兰顿蚂蚁等，有兴趣的可以研究一下。

至于我是怎么发现的。。。

你们知道有个手游叫the sandbox吗？（一度是我除了围棋以外唯一玩的手游）。它采用了wireworld规则来设计电路，不过游戏本身其实也是复杂元胞自动机的概念（包括落沙，水流处理等），是真正的“沙盒”游戏。评论里还提到了The Powder Toy，也是“沙盒”游戏非常好的示范。

等我学会了GPU编程，好想自己写一个巨大无比的sandbox来玩玩啊。