Minecraftで始める論理設計学

この記事は、team411アドベントカレンダー Advent Calendar 2024の18日目の記事です。
昨日はのぶさんの「2段階認証を楽に突破しよう」でした。弊学で有名な拡張機能の舞台裏が見れて面白かったです。

はじめに

弊学では、2年前期に論理設計学やL演習と題して論理回路の設計手法を学ぶ授業があります (私はM先生の論理設計学とS先生のL演習を受けました)。この授業ではひたすらに数式を書いて論理回路を設計するのですが、これをMinecraftに応用することでより直感的に理解できるのではないかと考えました。
この記事では、論理設計学で学ぶ手法を紹介しつつ、それを用いてMinecraft内でレッドストーン回路を実装する方法を紹介します。

この記事で紹介すること

• ブール代数
• Minecraftが論理的完全系であることの証明
• 順序回路とD-FF
• 状態遷移図と遷移表
• カルノー図による最小積和系の導出
• 回路図の設計
• Minecraftが正則言語を受理できることの証明 (応用)
• Minecraftがチューリング完全であることの証明 (応用)

この記事で紹介しないこと

• レッドストーン回路の基本

ブール代数

論理変数の導入

これから論理回路などを扱う上で、論理を数学の記号として表現できると便利です。そこで、論理変数を導入します。論理変数は真理値を持つ変数で、任意の論理変数 $x$ は $x \in \{0, 1\}$ を満たします。ここで、$0$ は偽、$1$ は真を表します。Minecraft上で論理変数を扱うときは、レッドストーン信号がある (強度が1以上) の時に $1$ 、ない (強度が0) の時に $0$ とします。

Minecraft上の論理変数。手前を0 (偽)、奥を1 (真)とみなす。

論理変数上の演算

論理変数に対して幾つかの演算を定義します。

否定

論理変数 $x$ に対する否定の記号を $\overline{x}$ で定義します。離散数学風に書けば $\overline{x} \coloneqq \lnot x$ です。その意味は次の表のように定義されます。

$x$	$\overline{x}$
0	1
1	0

Minecraft上では、レッドストーントーチ (以下トーチ) が刺さったブロックに対して信号を与えることで否定を表現できます。

Minecraft上の否定 (例)

論理和

論理変数 $x, y$ に対する論理和を $x + y$ で表します。離散数学風に書けば $x + y \coloneqq x \lor y$ です。その意味は次の表のように定義されます。

$x$	$y$	$x + y$
0	0	0
0	1	1
1	0	1
1	1	1

Minecraft上では、単にレッドストーンパウダーを繋げるだけで表現できますが、実装時には逆流に注意する必要があります。

Minecraft上の論理和 (例)

論理積

論理変数 $x, y$ に対する論理積を $xy$ や $x \cdot y$ で表します。離散数学風に書けば $x \cdot y \coloneqq x \land y$ です。その意味は次の表のように定義されます。

$x$	$y$	$xy$
0	0	0
0	1	0
1	0	0
1	1	1

Minecraft上では、下のように表現できます。

Minecraft上の論理積 (例)

また、

$$xy = \overline{\overline{x} + \overline{y}},$$

であることに注意すれば、上の方法以外でも様々な方法で表現できます。

演算の優先順位

ブール代数の演算の優先順位は次の通りです。

$$\overline{x} > xy > x + y$$

ブール代数の色々

本来、授業ではこの演算についての性質を色々学びますが、ここでは割愛します。

Minecraftとブール代数

論理関数

上のように定義した論理変数に対して、通常の代数と同じように論理関数を考えます。この関数は論理変数を引数に取り、論理変数を返すものです。例えば、次のような関数が考えられます。

$$f(x, y) = x\overline{y} + \overline{x}y.$$

任意の関数を表現するのに十分な演算を持つことを論理的完全系と言います。例えば、$\{\mathrm{NOT}, \mathrm{OR}\}$ は論理的完全系です。よって、上で定義した3つの演算も論理的完全系です。

Minecraftが論理的完全系であることの証明

上でも紹介した通り、Minecraft上で論理和と否定を表現できるので、Minecraftは論理的完全系であると言えます。要するに、Minecraft上で任意の論理関数を表現できるということです。

組み合わせ回路と回路図

ある論理関数を表現する回路を組み合わせ回路と言います。組み合わせ回路は、入力に対して常に同じ出力を返す回路です。
組み合せ回路を回路図の形で書けるようにするため、以下の論理回路記号を導入します。

論理回路記号

この記号を使って、論理関数を表現する回路図を書くことができます。例えば、上で紹介した関数 $f(x, y) = x\overline{y} + \overline{x}y$ を表現する回路図は次のようになります。

論理回路記号の例

順序回路とD-FF

順序回路とは

順序回路は、出力が入力と過去の入力に依存する回路です。数学的に書けば、順序回路は内部に時刻 $t$ についての状態 $Q(t)$ を持ち、組み合せ回路、

$$f: (I(t), Q(t)) \mapsto (O(t), Q(t + 1)),$$

によって出力 $O(t)$ と次の状態 $Q(t+1)$ を決定します。ここで、$I(t)$ は時刻 $t$ での入力を表します。$Q(t)$を $Q^t$ (「$Q$ の $t$ 乗」の意味ではない) と書くこともあります。
また、上に出てきた変数はほとんど全て論理変数ですが、$Q(t)$ は論理変数のベクトル $Q(t) \in \{0, 1\}^n \, (n \in \mathbb{N})$ であることに注意してください。要するに、状態は複数の論理変数の組み合わせで表現されます。

これを実際の回路に落とし込む時には次のような構成を取ります。

ミーリー型の順序回路

順序回路はこのような回路の上で、入力に応じて次々と状態や出力を変化させます。

フリップフロップ

順序回路において、状態の部分では次の入力が来るまでの間に値を保存しておいたり、入力が来た後に値を適切に更新する必要があります。そこで、フリップフロップ (FF) と呼ばれる記憶回路が使われます。ここでは、D-FFと呼ばれるフリップフロップを紹介します。

D-FFの論理回路記号

D-FFは同期信号 $CLK$ (左下の入力) がONになるタイミングで、入力 $D$ (左上の入力) の値を保存します。保存された値は常に出力 $Q$ (右上の出力) に出力されます。(右下の出力 $\overline{Q}$ は $Q$ の否定です。)

Minecraft上ではリピーターロック機能を用いて次のように実装できます。

Minecraft上のD-FF ($\overline{Q}$ は省略)

状態遷移図と遷移表

ここまでで紹介したような回路を設計する際に便利なツールとして、状態遷移図と遷移表があります。

状態遷移図

状態遷移図は次のような図です。

状態遷移図

読み方のルールは以下の通りです (先生によって違うことがあるので注意)。

• 丸や二重丸は状態を表す
• 状態は (上の図では) 2つの論理変数で表現され、それらを並べて書く
  • 例：$Q = (0, 0)$ なら状態に $00$ と書く
• 矢印は遷移を表す
• 矢印には遷移条件と遷移時の出力を書く
  • 例：$00 \stackrel{0/1}{\to} 01$ なら、$Q = 00$ の時に入力が $1$ だったら $Q = 01$ に遷移し、出力は $0$ になる
• startの矢印が指す先は初期状態を表す

ちなみに、上の図は入力として2進法の自然数を最上位ビットから読んだ時に、その数が3の倍数かどうかを判定する状態遷移図です。各状態はmod3を表します。mod3が0の時に1を出力することから、状態 $00$ を二重丸で表示しています。

遷移表

もしかすると、遷移表の方が直感的かもしれません。上の状態遷移図を遷移表にすると次のようになります。

現在の状態 ($Q^t = Q_1^tQ_0^t$)	$x=0$	$x=1$
$00$	$00, 1$	$01, 0$
$01$	$10, 0$	$00, 1$
$10$	$01, 0$	$10, 0$

例えば1行目は、状態 $00$ の時に入力が $X=0$ なら次の状態は $00$ で出力は $1$ になり、入力が $X=1$ なら次の状態は $01$ で出力は $0$ になるということを表しています。

(別にどっちでもいいのですが、) 添え字の順番が $Q_1^tQ_0^t$ の順であることに注意してください。

カルノー図による最小積和系の導出

本来はこの前に含意表を用いて状態数の削減を試みますが、ここでは先の例が状態数最小であることを認めて進めます。

ここからは、上の遷移表を実際にレッドストーン回路に落としていくことを考えます。記憶回路の部分にはD-FFを用いるというのは順序回路とD-FFで説明した通りです。一方、順序回路の組み合わせ回路部分の設計には、まず該当する論理関数を論理変数の演算で表す必要があります。

まずは、上の遷移表を愚直に式に起こしてみましょう。例として、遷移表の出力 $y^t$ について真理値表を作ると次のようになります。

$Q_0^t$	$Q_1^t$	$x^t$	$y^t$
0	0	0	1
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	1
1	1	0
1	1	1

よって $y^t$ についての式は次のようになります。

$$y^t = \overline{Q_0^t}\,\overline{Q_1^t}\,\overline{x} + Q_0^t\overline{Q_1^t}x.$$

このように、積を取った後に和をとる形の式を積和系と言います。(反対に、和を取った後に積を取る $(a + b)(c + d)$ みたいな形の式を和積系と言います。)

しかし、実はこの $y^t$ の式は冗長です。より短い積和系 (最小積和系) にすることができます。
そのために、カルノー図というものを使います。

カルノー図

カルノー図の作成方法は次の通りです。

1. 真理値表の結果が $1$ になる場所を見つける
2. その場所に相当するカルノー図のマスに $1$ を書く
3. 真理値表で結果が定まらない場所 (上の例なら $Q_0^t = Q_1^t = 1$ の時は定義されていない) ところに「＊」を書く (ドント・ケアと言う)

• 今回は3変数なので、表のサイズが2×4ですが、2変数や4変数の場合は変わります。
• 列について、01の次は11なので注意してください。

カルノー図が作成できたら、全ての1を覆うように、以下の条件を満たす長方形をいくつか見つけます。

1. 高さと幅が2のべき乗
2. 1または＊のみを含む
3. 表の左右の端と上下の端はそれぞれ繋がっているものとする
4. 長方形はできるだけ大きく、少なくする

上のカルノー図に対して長方形を書くと次のようになります。

カルノー図の長方形

カルノー図の長方形の行と列に対応する論理変数について、変化がない部分を取り出して、最小積和系を求めます。上の例では、次のようになります。

$$y^t = \overline{Q_1^t}\,\overline{Q_0^t}\,\overline{x} + Q_0^tx.$$

カルノー図は人間向けのやり方です。コンピュータに最小積和系を求めさせたい時は、クワイン・マクラスキー法 (QM法) を使います。

同様に、$Q_0^{t+1}, Q_1^{t+1}$ についても最小積和系を求めると次のようになります。

カルノー図の例

$$\begin{align*} Q_0^{t+1} &= \overline{Q_1^t}\,\overline{Q_0^t}\overline{x} + Q_1^t\overline{x}, \\ Q_1^{t+1} &= Q_1^tx + Q_0^t\overline{x}. \end{align*}$$

回路図の設計

最後に、上で求めた最小積和系を元に、回路図を設計します。

回路図

この段階まで来れば、あとは実際にMinecraft上で回路を構築するだけです。

Minecraft回路の様子

ブロックの色の意味はそれぞれ次の通りです。

• 空色：$x$
• 黄色：$Q_0^t$
• 橙色：$\overline{Q_0^t}$
• 黄緑色：$Q_1^t$
• 緑色：$\overline{Q_1^t}$
• 紫色：$Q_0^{t+1}$
• 青色：$Q_1^{t+1}$
• 桃色：$y^t$
• 白色：$CLK$

Minecraftが正則言語を受理できることの証明

ここからは応用編です。論理設計学の範囲を超える内容ですが、興味がある方は読んでみてください。詳しくは形式言語理論で勉強できます。

正則言語

正則言語の定義は割愛しますが、イメージとして、ある正規表現が表せる文字列全体の集合は全て正則言語です。逆に、正則言語に属する文字列の集合には、それを表す正規表現が必ず存在します。

ここで言う正規表現は拡張正規表現とは異なることに注意してください。

実は、全ての正規表現はそれに対応する状態遷移図が存在します。すなわち、Minecraftで任意の正規表現に対応したレッドストーン回路を作ることができます。
今回は正規表現 $E=1(01+10)^*$ を受理する回路を作ります。これは正規表現の数学的な表し方ですが、所謂「正規表現」風に書けば、/^1(01|10)*$/です。

正規表現から状態遷移図の変換

正規表現はそれを表す$\varepsilon$遷移付きNFA→DFA→状態遷移図という順番で変換することで状態遷移図を得ることができます。$E$ の状態遷移図は次のようになります。

正規表現の状態遷移図

上の説明、 オフチョベットしててごめんなさい。

状態遷移図から回路図の設計

カルノー図による最小積和系の導出や回路図の設計と同様に、カルノー図を用いて最小積和系を求め、回路図を設計します。

回路図

これをMinecraftで実装すると次のようになります。

これにより、Minecraftで正規表現を受理する回路を作ることができました。

同様の手順で、任意の正則言語に対応する回路を作ることができます。よって、Minecraftは全ての正則言語を受理できると言えます。

Minecraftがチューリング完全であることの証明

よく「Minecraftはチューリング完全だからCPUが作れる」なんていう説明がされているのをよく見ますが、なぜMinecraftがチューリング完全なのかまで説明してくれている人はあまり見かけません。ここでは、Minecraftがチューリング完全であることを証明します。

チューリング完全とは

チューリング完全とは、チューリングマシンと同じ計算能力を持つことを言います。これは、計算能力の限界を示すもので、身の回りの多くのプログラミング言語や計算機がチューリング完全であることが知られています。チューリング完全性があれば、実用上のあらゆる計算を行うことができます。

ある計算機がチューリング完全であることを示すのは簡単で、その計算機でチューリング完全性を持つ別の計算機と同じ計算を行うことができれば良いだけです。今回は、ルール110のセルオートマトンをMinecraftで実装することで、Minecraftがチューリング完全であることを示します。
(つまり、さっき例で挙げた「Minecraftはチューリング完全だからCPUが作れる」と言う主張はそもそも論理が逆だったんですね。)

ルール110のセルオートマトン

セルオートマトンとは、状態を持つことができるセルが一直線上に並んだマシンです。セルの状態は周囲のセルの状態によって刻々と変化します。
特に今回は、$p$ 番目のセルの状態を $Q_p^t \in \{0, 1\}$ とします。
ルール110は全てのマスについて、そのマスと左右のマスを見て、次の表の通りに状態を変化させるセルオートマトンです。

左	自分	右	次の状態
1	1	1	0
1	1	0	1
1	0	1	1
1	0	0	0
0	1	1	1
0	1	0	1
0	0	1	1
0	0	0	0

状態の変化は次のようになります。

このセルオートマトンは、チューリング完全であることが知られています。

ちなみにこれを20ステップ進めると次のようになります。

Minecraftでルール110のセルオートマトンを実装

上の表をそのまま遷移表として、ある地点 $p$ における時刻 $t$ のセルの状態を $x_p^t$ とすると、最小積和系は次のようになります。

$$x_p^{t+1} = \overline{x_p^t}x_{p+1}^t + x_p^t\overline{x_{p+1}^t} + \overline{x_{p-1}^t}x_{p+1}^t + \overline{x_{p-1}^t}x_p^t$$

回路図は次のようになります。

ルール110のセルオートマトンの回路図

これをMinecraftで実装すると次のようになります。

これにより、Minecraftがチューリング完全であることが示されました。

まとめ

この記事では、論理設計学の授業で学んだ手法を用いて、レッドストーン回路を設計しました。今回作成したワールドはこちらで配布しています。是非参考にしてください。

明日はみみさんの「CPU始めました」です。是非読んでみてください。