はじめに
コンピュータ系サークル TSG は Slack での交流が活発です。そんな TSG Slack では日夜さまざまな bot が動いています。その中のひとつが、ハイパーロボットです。
図中の赤、青、黄、緑の丸はロボットを表しています。それぞれのロボットは上下左右に動かすことができ、動かされたロボットは壁あるいは他のロボットにぶつかるまで移動し続けます。このゲームの目的は、指定された手数で、星のあるマスに同じ色のロボットをちょうど着地させることです。ちなみにこの bot の元ネタはハイパーロボット (原題: Ricochet Robots) というボードゲームです。
話は変わりますが、TSG は難解プログラミング言語を使ったコードゴルフの大会をよく開催しています。大会で使われる言語の中には部員たちが自作した言語も含まれており、音ゲーをもとにした言語、Slack のメンションをもとにした言語、高次元トーラス言語などさまざまなものがあります。また、KMC という別のサークルでもこの大会のために部員が言語を作るイベントがあったようで、テトリスをもとにした言語、バブルソートをもとにした言語、古典派音楽理論をもとにした言語、メルセンヌ・ツイスタをもとにした言語、マインスイーパーをもとにした言語など溢れんばかりの独特な言語が作られています。
ということは、そろそろハイパーロボットをもとにした言語が作られても良いはずです。ハイパーロボットで「計算」を行うにはどのように仕様を定めれば良いのでしょうか？
論理演算のアイデア
現代のコンピュータの礎となっている概念といえば、ブール代数による論理演算です。各変数が 0 か 1 の値を取り、入力から出力が定まるような論理ゲートを、ハイパーロボットで構成してみます。
まず以下のようなボードを考えてみましょう。
X や Y を上下に動かしたあと、A は右側に到達できるでしょうか？
答えは、「X と Y が両方上側にあるとき、かつそのときに限り、A が右側に到達できる」です。
 |
 |
 |
 |
これに以下のような目印をつけるとどうでしょう？
先ほどの 4 通りの組み合わせは、以下のようにまとめられます。
| X | Y | A | |
|---|---|---|---|
| 0 | 0 | 1 | |
| 0 | 1 | 0 | |
| 1 | 0 | 0 | |
| 1 | 1 | 0 |
論理回路としては、これは NOR ゲートであるといえます。
論理演算のうち、NOR ゲートと NAND ゲートは完全性を持つ（その演算のみの組み合わせによって任意のブール関数を構成することができる）ことが知られています。これでハイパーロボットで任意の演算ができる可能性が見えてきました。
ちなみに、目印の 0 と 1 を置き換えることで、NOR ゲート以外にも NAND ゲート、OR ゲート、AND ゲートが構成可能です。
インターフェイスを決める
上記の方法で論理演算が可能なことはわかりましたが、これを組み合わせるとなると難しいです。よって次に、インターフェイスを決めます。
すべてのゲートはいくつかの入力と出力を持ちます。入力はある通路にロボットが左から入ってくるかどうか（入ってきたら 1、入ってこなかったら 0）、出力はある通路からロボットが右に出ていくかどうか（1 だったら出ていく、0 だったら出ていかない）としましょう。
このとき処理順序としては、
- X が入ってくる（入ってこないかもしれない）
- Y が入ってくる（入ってこないかもしれない）
- 中で何か決まった処理をする
- A が出ていく（出ていかないかもしれない）
となります。ただし中で行う処理の決まりごととして、
- X と Y の入ってくる順序によらない
- 入ってきた X と Y は動かさない
と定めます。これにより、ゲートを組み合わせ、決まった処理を順序通り実行するだけで、複雑な演算が可能になるはずです。
では、このインターフェイスに従って必要なゲートを作っていきましょう。
論理回路 ①
NOT ゲート
まずもっともシンプルなゲートとして、NOT ゲートは以下のように作ることができます。
X が入ってきたあとの処理は
A ↓ →
です。X が入ってきたら A は出ていくことができず、X が入ってこなかったら A は出ていくことができます。このとき手数は 2 です。（出力を下向きにして組み合わせるときは、最後に A を右へ動かす処理を省くことができるので、手数 1 とも言えます。）
NOR ゲート
最初に触れたとおり、NOR ゲートは以下のように作ることができます。
X と Y が入ってきたあとの処理は
A ↓ →
です。X または Y が入ってきたとき、かつそのときに限り A は出ていくことができません。手数は NOT ゲートと同じく 2（あるいは 1）です。このゲートは n 入力の場合に一般化することができます。そうすると NOT ゲートは NOR ゲートの 1 入力版であることがわかります。
OR ゲート
OR ゲートは以下のように作ることができます。
X と Y が入ってきたあとの処理は
0 ↓ A →
です。X と Y どちらかで 0 をせき止め、0 がせき止められたら A が出られます。手数は 2 です。よく見ると、この OR ゲートは NOR ゲートの出力に NOT ゲートをかけたものであることがわかります。こちらも n 入力の場合に一般化できます。
AND ゲート
AND ゲートはもう少し複雑で、以下のように作ることができます。
X と Y が入ってきたあとの処理は
0 ↓ 1 ↓ A →
です。X が入ってきたら 0 がせき止められ、Y が入ってきたら 1 がせき止められます。両方がせき止められたら A が出られます。手数は 3 です。これもよく見ると、入力に NOT ゲートをかけて NOR ゲートに通していることがわかります。うまくやると n 入力の場合に一般化できます。
値の複製
COPY ゲート
今までに見てきたゲートは入力を消費してしまうという問題があります。そこで論理ゲートではありませんが、値を複製するようなゲートを作る必要があります。
X が入ってきたあとの処理は
B ↓ A ↓ → B →
です。ちょっとややこしいですが、X が入ってこなかったら A と B が上に溜まってしまい、出ていきません。X が入ってきたら A と B は上に行かず、右に出ていきます。手数は 4 です。これも n 出力の場合に一般化できます。
COPY-NOT ゲート
入力を複製するだけでも面倒なことがわかりました。色々な回路を組み合わせることを考えると、もう少し簡略化したいです。実は上のゲートは、少し変えると NOT も出力できるようになっています。
X が入ってきたあとの処理は COPY ゲートと同じく
B ↓ A ↓ → B →
です。X が入ってきたら A, B は上にあるので A のみが出ていき、X が入ってこなかったら A, B は下に行くので B のみが出ていきます。これも n 出力の場合に一般化できます。
論理回路 ②
XOR ゲート？
XOR ゲートは入力が 1 つだけ来たときのみ出力すれば良いので、以下のようなものが考えられます。
X と Y が入ってきたあとの処理は
1 ↓ → 0 ↓ → A → ↑ →
です。0 か 1 どちらか 1 つのみが右下の溝にはまれば、A が出ることができます。手数は 7 です。
ただし、ここで問題になるのがゲートの再利用性です。将来的にループ構造によって計算を行うとき、論理ゲートは何度も繰り返し使える必要があります。そのためには、論理ゲートは一定の手順によってもとの状態に復元できる必要があります。実は今までの NOT ゲート、NOR ゲート、OR ゲート、AND ゲート、COPY ゲートは、記した手順を逆に行うことでもとの状態に復元することができるようになっています。
このゲートはどうでしょう？ 例えば X だけが入ってきたとき、1 を下ろしたあと右に動かしてしまうと、1 はその後もとの位置に戻ることができなくなります。
再利用可能な XOR ゲート
さて、今までの OR 演算や AND 演算は NOT 演算と NOR 演算の組み合わせがもとになっているのでした。いったん XOR 演算をこれらの組み合わせに変換してみましょう。XOR 演算子を 、NOR 演算子を
で表すこととします。XOR 演算は NOT 演算と NOR 演算を用いて
のように変形できます。ここから以下のような回路を作ることができます。（めっちゃ縦に長いです。）
わかりやすくするために、X, ¬X, Y, ¬Y がどこに来るのか印がついています。X と Y が入ってきたあとの処理は
0 ↓ 1 ↓ → 0 → 2 ↓ 3 ↓ → 2 → 4 ↓ 5 ↓ A →
で、手数は 11 です。
複雑なように見えて、今までのゲートの単純な組み合わせになっています。もっと小さな XOR ゲートを作ることもできるのかもしれませんが、ゲートの組み合わせによって回路が作れるというのが重要なポイントです。
加算器
半加算器
ようやく半加算器です。半加算器は XOR ゲート 1 つと AND ゲート 1 つを合わせたものです。XOR ゲートのロボット 5 が AND に使えるので、使って効率化を図ります。
A と B が入力、S がその桁の和、C が繰り上がりを表しています。A と B が入ってきたあとの処理は
0 ↓ 1 ↓ → 0 → 2 ↓ 3 ↓ → 2 → 4 ↓ C ↓ 5 ↓ S → C →
で、手数は 13 です。XOR のロボット 5 を 2 体に増やして、S を足止めしつつ C として出力できるようになっています。
全加算器
全加算器は半加算器 2 つと OR ゲート 1 つを合わせたものです。
手数は、
- 半加算器 ① … 13
- ① の C を曲げる … 2
- 半加算器 ② … 13
- OR … 2
で、30 になります。
複数ビットの加算器
図がやばくなるので描きたくありませんでしたが、4 ビット加算器を描きました。
テストしていませんが、多分ちゃんと動くでしょう！
おわりに
さて、ハイパーロボットで加算器を作ることができました。
足し算をするのにここまでかかるので、これでプログラミングなんかやりたくないですね。
プログラムとして動かすにはループや入出力が必要なので、それをどうするか決めなくてはいけません。
大変なので、多分続かないです……？
編集履歴
2022-01-14
- 半加算器の繰り上がりの部分が間違っていたので修正しました。ちゃんとテストしないから……。テスト用プログラムを作りたいですね。
- COPY-NOT ゲートがもっと縮むことに気づいたのですが、（次があったら）次に回します。
