据说Minecraft是图灵完备的

2 年 ago

科, 颖

2 minutes

首先

通过朋友听说Minecraft是图灵完备的，我开始怀疑真实性，于是进行了一番调查。

这篇文章几乎没有提及Minecraft的指令方块、红石电路之类的内容。我知道这篇文章有些奇怪，还请多多包涵。

如果你已经知道图灵完备是什么的话，请跳过本节，我们将先对图灵完备进行解释，然后进入正题。

「什么是图灵完备」呢？(有点儿柔和)

「計算機」には色々なものを考えることができます。足し算しかできない計算機とか、”0″と出力することしかできない計算機とか。そんな計算機たちの中でも、めちゃくちゃすごくて、他の計算機が計算できることは何でも計算できる「スーパー計算機」を考えましょう。

当一台计算机具有与这台”超级计算机”相同的能力时，该计算机被称为”图灵完备”。也就是说，”图灵完备”的计算机可以模拟(reproduce)其他计算机能够执行的任何计算。太厉害了！

「图灵完备」是什么意思？(硬循说)

总结

1936年にイギリスの数学者であり計算機科学者でもあるアラン・チューリングが、チューリングマシン(以下、TM)という仮想機械を発表しました。この機械は、「計算」とは何なのか、「計算機」とは何なのかを科学的に議論するための、理想化された機械であり、

一条无限长的可读写的磁带
用来读写磁带里存储的信息的磁头
用来存储和控制机器内部状态的控制单元 (有限自动机)

它由磁带组成。磁带被分割成相同大小的格子（单元），每个格子可以使用头部来读写磁带符号。关于磁带符号将在后文解释。

此外，根据TM的内部状态和从头部读取的信息的组合，它将执行下一步的操作。

ヘッド位置のテープに情報を書き込む
機械の内部状態を変える
ヘッドを右か左に一つ移動する

形式的定义

对于TM（图灵机）的形式定义如下，有以下7个要素组成。

M = <Q,Σ,Γ,δ,b,q_0,q_f>

$Q$：状態の有限集合
$Σ$：入力アルファベット
$Γ$：テープ記号 $(Σ \subset Γ)$
$δ$：遷移関数
$b$：空白記号 $(b \in (Γ-Σ))$
$q_0$：初期状態 $(q_0 \in Q)$
$q_f$：受理状態 $(q_f \in Q)$

遷移函數 $δ$ 是一個從 $(Q × Γ)$ 映射到 $(Q × Γ × d)$ 的映射 (其中 $d ∈$ { $L,R$ })。

举个例子

δ(q,a) = (r,b,R)

は、「現在の状態が$q$であり、ヘッドの先の記号が$a$であれば、状態を$r$に移し、ヘッドの先に記号$b$を書き込んでから、ヘッドを$R$方向(右方向)に1つずらす」ことを意味しています。

また、後の記述のために、$Σ$のスター閉包$Σ^\star$を定義します。スター閉包とは、長さが0である空記号列$ε$を含めて、$Σ$上で作り得るあらゆる記号列の全体からなる無限集合を表します。

如果说$Σ=${ $0,1$ }，那么$Σ^\star = ${ $ε,0,1,00,01,10,11,000,001,010,…$ }。

行动

对于输入字符串 $w(\in Σ^\star)$ ，图灵机的操作如下。

まず最初に、テープ上の連続した区画に入力記号列$w$が書き込まれたものが用意され、ヘッドは$w$の左端に置かれます。なお、そのほかの部分には空白記号$b$が書き込まれています。さらに、機械の内部状態が初期状態$q_0$に設定され、TMの動作が開始されます。その後は遷移関数$δ$に記載された動作に従って逐次動作が続けられます。

TMの現在の状態が$q$であり、ヘッド先の記号が$a$であって、$δ(q,a)$が定義されていない場合、TMはそこで動作を停止します。TMが停止したとき、その状態が受理状態$q_f$であれば、$w$はTMにより受理されるといいます。また、$w$がTMにより受理されない場合とは、

当未能达到受理状态而达到最终计算状态时
当无法达到最终计算状态而永远继续计算时

这是限定在这个时候的。

万能图灵机

我们可以考虑各种不同的转移函数。

假设对于所有的$q \in Q$和$x \in Σ$，存在以下的转移函数。

δ(q,x) = (q,`0',R)

无论内部状态或者头部前面的符号是什么，在将符号$0$写入头部之后，向右移动一个单位的函数被表示出来。拥有这样的转移函数的机器也是图灵机中的一种，但可以说其计算能力较低。

在这种情况下，如果能够正确构建转移函数，就可以创建一台“无论是什么图灵机，都可以模仿它”的图灵机。换句话说，对于任何其他图灵机能够计算的计算，都可以创建一个可计算的图灵机。这种图灵机被称为通用图灵机。

当某个计算机机制具有与万能图灵机相同的计算能力时，该计算模型被称为图灵完备。

图灵完备的解释就是这样。辛苦了。

要证明一个东西是”图灵完备”的，怎么做？

为了证明Minecraft是图灵完备的，只需在Minecraft中模仿“已知是图灵完备的”某种东西””。因为通过模仿这种“东西”，间接地可以模拟所有的图灵机运算。

例如，作为图灵完备的例子，有以下几种情况。

一般的なプログラミング言語全て – All common programming languages
純LISP – Pure LISP
SQL – SQL
HTML5 + CSS – HTML5 + CSS

ウルフラムの2状態3記号チューリングマシン – Wolfram’s 2-state 3-symbol Turing machine (イギリスの学生さんがチューリング完全性を証明しました。なんと証明当時は20歳！) – A British student proved Turing completeness for this machine, and he was only 20 years old at the time!

ポケモン黄色 – Pokemon Yellow (バグを利用することによって、ゲーム操作によりアセンブリを書き換え、チューリング完全性を満たすゲームに書き換えることができるそうです。) – It is said that by exploiting bugs and manipulating game operations, one can rewrite the assembly and turn Pokemon Yellow into a game that satisfies Turing completeness.

マジック・ザ・ギャザリング – Magic: The Gathering
We always knew Magic: the Gathering was a complex game. But now it’s proven: you could assemble a computer out of Magic cards.
マジック・ザ・ギャザリングが複雑なゲームであることは知られている。しかし今や証明されたのである: マジックのカードを使ってコンピューターをも組み立てられる事が。
(From the link provided)

有很多事情呢。其中有些让人感到“嗯？”的东西也有…。

しかし、これらをMinecraft上で実装するのは厳しそうです。そこで、何か他にチューリング完全であるものを実装している人はいないかと調べてみると、いくつか見つかりました。その概要とともに紹介したいと思います。

实施示例

脑f * ck

简而言之

Brainf*ck是一种被设计为编译器尽可能小巧的编程语言，它的可读性非常低，但具备图灵完备性。由于包含粗俗词汇，常被打码隐藏。

Brainf*ckプログラムは、以下の8個の命令から成り、それ以外の文字は無視され、読み飛ばされます。

> ポインタをインクリメント

< ポインタをデクリメント

+ ポインタが指す値をインクリメント

– ポインタが指す値をデクリメント

. ポインタが指す値を出力

, 入力から1バイト読み込み、ポインタが差す先に入力

[ ポインタが指す値が0なら、対応する]の直後にジャンプ

] ポインタが指す値が0でないなら、対応する[の直後にジャンプ

程序示例

这是用Brainf*ck编写的“Hello, world!”程序。

+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-.
------------.<++++++++.--------.+++.------.--------.>+.

我不知道呢。

介绍

有一台可以执行Brainf*ck语言程序的计算机或者已经实现了Brainf*ck解释器。

Brainfuck interpreter using CommandblocksJS

ライフゲーム

总结

生命游戏是由英国数学家约翰·霍顿·康威于1970年发明的模拟游戏，通过简化的模型再现了生命的诞生、进化和淘汰等过程，也是最著名的细胞自动机示例之一。

元胞自动机

セル・オートマトンとは、格子状のセルと単純な規則による、離散的な計算モデルです。有限種類の状態を持つセル(Cell、細胞のような単位)によってセル・オートマトンは構成され、次々に個々のセルの状態が変化します。その変化は、ある時刻$t$においてのセルの状態、および近傍のセルの状態によって、次の時刻$t+1$、すなわち新たな世代での各セルの状態が決定されます。

规则

在生命游戏中，只有初始状态决定了后续的状态。每个细胞有两种状态，分别是”生”和”死”（或者”1″和”0″）。一个细胞在下一步（一代）的状态由相邻的8个细胞在当前一代的状态来决定。细胞的生死遵循以下规则。

介绍

我们已经实现了一个可以模拟生命游戏的环境。

YouTube – 【Minecraft】ライフゲームシミュレータ【結月ゆかり解説】

一维元胞自动机

概述

这是上面提到的元胞自动机的一维版本（也称为基本元胞自动机）。

基本的な動作は同じで、1次元で各セルは2つの状態(生 or 死、1 or 0)をとることができます。あるセルとその両側の3つのセルで近傍を構成するので、1つの近傍がとりうるパターンは $2^3=8$ 種類となり、規則はそれらのパターンについて、そのセルが次世代に1と0のどちら状態となるかを決定します。従って、規則群の組合せは $2^{2^3}=2^8=256$通りとなります。

それら256種類のセル・オートマトンは、一般にイギリスの理論物理学者であるスティーブン・ウルフラムが考案した0から255までのルール番号で参照され、これをウルフラム・コードと呼びます。Rule 110セル・オートマトンは、以下の規則により世代が更新していくオートマトンです。

現在の状態中央のセルの次の状態0 0 000 0 110 1 010 1 111 0 001 0 111 1 011 1 10

这个被称为「Rule 110」的是因为将中间细胞的下一个状态排列为01101110，将这个二进制数转换为十进制数为110。

假设有以下的比特串。

…100111011001…

按照上面提到的规则对该比特串进行操作，结果如下所示。

…十万千百十一十一十一十……

両端は無限に0が並んでいるとします。分かりやすいように一部を強調して表示してみます。

…1001 110 11001…
↓
…10110 1 111011…
↓
…一零一一零一一一一零一一一一…

像这样无限地进行计算。

これらのセル・オートマトンの挙動を見るために、三角形のような図形を描画することがあります。描画される図形は、1ヶ所だけ1にした初期状態からの、セル・オートマトンの変化の様子を示しており、図の各行がセル・オートマトンの1世代の履歴です。また、一番上の行が$t=0$であり、各ピクセルは、0を白、1を黒で描画しています。

规则90的一维元胞自动机产生的图形是典型的分形图形，它是谢尔宾斯基的三角形图案。

現在の状態中央のセルの次の状態0 0 000 0 110 1 000 1 111 0 011 0 101 1 011 1 10

介绍

実はRule 110のセル・オートマトンは、チューリング完全であることが知られています。以下の動画では

规则126
规则30
规则110
规则150

将介绍细胞自动机。

YouTube – Elementary Cellular Automaton In Minecraft

其他

在Minecraft中，有相当多的人是将CPU和文字处理器制作成了一个奇妙的事实。真是厉害啊…

YouTube – Minecraft Redstone Computer Word Processor [1024 subscriber special]

最後

というわけで、Minecraftは余裕でチューリング完全のようです。コマンドブロックやレッドストーン回路を駆使すれば何でもできそうですね。(調べている途中で、Minecraftでパックマンを実装したとか、ポケモン赤を実装したとかも出てきました。もはや訳が分かりません。)

如果心情好的话，我想亲自在Minecraft中尝试实现细胞自动机。

参考资料

「文献」といっていいのかわかりませんが、参考にさせていただきました。