Conditions【Turing Complete編】

2023年9月1日2023年10月17日

Conditionsステージ

Conditionsステージのゴールは、入力バイトデータがビットコードに応じた条件を満たすかを判定する回路を組むことです。

ステージの回路の入出力は次の通りです。

入力	・上のInput端子･･･ビットコード。3ビット ・下のInput端子･･･バイトデータ
出力	・Output端子･･･判定結果：1ビット

ビットコード	判定処理	出力
000b	判定しない	Outputは常にOFF
001b	入力バイトデータがゼロか	0ならOutputはON、それ以外ならOFF
010b	入力バイトデータが0より小さいか	0より小さいならOutputはON、それ以外ならOFF
011b	入力バイトデータが0以下か	0以下ならOutputはON、それ以外ならOFF
100b	判定しない	Outputは常にON
101b	入力バイトデータが非ゼロか	0でなければOutputはON、それ以外ならOFF
110b	入力バイトデータが0以上か	0以上ならOutputはON、それ以外ならOFF
111b	入力バイトデータが0より大きいか	0より大きいならOutputはON、それ以外ならOFF

Conditionsステージを解く

1：シミュレーターのナンバーフォーマットを切り替える

0より小さいパターンが存在するということは、入力バイトデータは符号つき8ビットと考えるということです。

左上のアイコン群の一番右アイコンを押して、「255」から「-1」にします。これでナンバーフォーマットを切り替わります。

2番目のInputのランプをON・OFFすると負の数を表現できていることを確認できます。

2：入力のビットコード側の設計方針を決める

今回の回路には2つの入力があります。

・ビットコード

・バイトデータ

まずはビットコード側の入力から攻めていきましょう。

ビットコードは3ビットであり、それぞれ違うパターンで、合計8パターンあります。それぞれのパターンが選ばれたときにONになるワイヤーが用意できればよいはずです。

これまで何度も登場していますが、8 Bit Splitterと3 Bit decorderの出番になります。

3：入力のバイトデータ側の設計方針を決める

次に、バイトデータ側の入力を考えます。

入力バイトデータとゼロを大小比較する仕組みを実装することになります。

比較対象がゼロなので、次のように考えます。

入力バイトデータのどこかの桁に1が1つでもあれば、0ではありません。

このような1の有無はORで判断できます。ORゲートを通した結果を中間結果Pと呼ぶことにします。

Pに注目すれば、ゼロとの一致・不一致は容易に判定できます。

[1]ゼロとの不一致、すなわち非ゼロとの一致を識別する

入力バイトデータが非ゼロかどうかは、中間結果Pと1をANDゲートに通せば判断できます。

[2]ゼロとの一致を識別する

中間結果PをNOTゲートで反転させれば、入力バイトデータが0000 0000bのときだけ、1になります。あとは、その反転結果と1とANDゲートに通せばゼロか否かを判断できます。

ここまではゼロとの一致回路の設計になります。

[2]ゼロより小さいを識別する

入力バイトデータの最上位ビットが1であれば、他の桁がどうなっていても、常にゼロより小さくなります（-128～-1）。

[3]ゼロより大きいを識別する

「入力バイトデータの最上位ビットが0」かつ「最上位ビット以外に1が1つでもある」ならば、ゼロより大きくなります（1～127）。

[4]ゼロ以上、ゼロ以下を識別する

「以上」（あるいは「以下」）については、「0と一致」＋「より大きい」（あるいは「より小さい」）と考えます。「＋」は「または」を意味するので、ORゲートを使えばよいのです。

以上で回路の設計方針を終えます。

なお、まとめて一気にやろうとすると思い悩むかもしれません。また、今回のステージの回路はキャンバスがとても狭いです。

条件を実現する回路を徐々に組んでいくと、回路の見通しが悪くなりますし、配置がうまくいかず手戻りが発生する可能性が高いです。

そこで、条件ごとに分けて回路を組んでいき、その回路を説明します。最後にキャンバスに納まるように、回路を最適化させつつ統合させていきます。

4：ビットコードの解読回路を組む

よく登場する基本回路になります。

ビットコードは3ビットなので、8 Bit Splitterコンポーネントの出力は3本しか使いません。素直に3 Bit decoderコンポーネントに直結します。

5：ビットコード000bのための回路を組む

ビットコードが000bのときは常に出力端子がOFFになるようにします。

このとき、3 Bit decoderコンポーネントの0番ピン^[1]ピンは0番から7番まであるものとしました。がONになります。NOTゲートを通せば、このビットパターンのときにOFFになります。

これを素直に回路に組むと次のようになります。

これでも問題ないのですが、ちょっと無駄があります。

「ビットコード000bのとき」

⇒「3 Bit decoderコンポーネントの0番ピンがON」

⇒「3 Bit decoderコンポーネントの0番ピン以外がOFF」

⇒「3 Bit decoderコンポーネントの0番ピンに何もつなげない。Conditons回路の出力端子につなげない。つまり出力はこの条件下で常にOFF」

結局のところ、NOTゲートとワイヤーを不要だったということです。これを回路にすると次のようになります。

6：ビットコード100bのための回路を組む

ビットコードが000bのときは常に出力端子がONになるようにします。

これは単純に出力端子と直結すれば実現できます。

7：ビットコードが101bのための回路を組む

ゼロとの不一致、すなわち非ゼロとの一致を識別させます。

入力バイトデータが非ゼロかどうかは、中間結果Pと1をANDゲートに通せば判断できます。

※Pは入力バイトデータの全桁をORゲートに通した結果です。

8：ビットコードが001bのための回路を組む

中間結果PをNOTゲートで反転させて、その反転結果と「3 Bit decoderの1番ピンからくる1（ON）」とANDゲートに通せばゼロか否かを判断できます。

入力バイトデータが0000 0000bのときだけ、中間結果Pが0なり、その反転が1になるからです。

9：ビットコードが010bのための回路を組む

入力バイトデータが0より小さいときに、出力端子をONにさせます。

「入力バイトデータが0より小さい」

⇒「入力バイトデータが負の数」

⇒「入力バイトデータの最上位ビットが1」（他の桁は任意）

これを回路にすると次のようになります。

10：ビットコードが111bのための回路を組む

入力バイトデータが0より大きいときに、出力端子をONにさせます。

「入力バイトデータが0より大きい」

⇒「入力バイトデータの最上位ビットが0」かつ「最上位ビット以外に1が1つでもある」

「入力バイトデータの最上位ビットが0」かつ「最上位ビット以外に1が1つでもある」という条件について、素直に回路を組むと次のようになります。

しかし、後半の条件「最上位ビット以外に1が1つでもある」に対応する回路が少し冗長です。

これは「どこかの桁に1が1つでもある」と言い換えても問題ありません。なぜなら、前半の条件で「最上位ビットが0」と確定しているからです。

「どこかの桁に1が1つでもある」ことを判定する回路はすでに登場しており、共通化も期待できます。

「入力バイトデータの最上位ビットが0」かつ「どこかの桁に1が1つでもある」という条件について、回路を組むと次のようになります。

11：ビットコードが011bのための回路を組む

入力バイトデーが0以下のときに、出力端子をONにさせます。

「入力バイトデータが0以下」

⇒「入力バイトデータが0」または「入力バイトデータが0より小さい」

比較回路の原型はすでに完成していますので、あとは組み合わせるだけです。

ところで、次の2回路は同値になります。

A	B	C	Y	Y’
0	0	0	0	0
0	0	1	0	0
0	1	0	0	0
0	1	1	0	0
1	0	0	0	0
1	0	1	1	1
1	1	0	1	1
1	1	1	1	1

これを踏まえると、回路の組み方としては次の2通りがあります。

回路2は先にORで組み合わせてから、（3 Bit decoderの3番ピンと）ANDを取っています。ゲートを節約できるので、こちらを採用します。

12：ビットコードが110bのための回路を組む

入力バイトデーが0以上のときに、出力端子をONにさせます。

「入力バイトデータが0以上」

⇒「入力バイトデータが0」または「入力バイトデータが0より大きい」

0以上というのは、入力バイトデータの最上位ビットが0と言い換えられます。これを回路に落とし込むと、上の回路よりすっきりします。

13：全パターンの回路を統合・最適化する

上記の回路に説明を入れると次のようになります。

14：テストする

クリアするとCONDコンポーネントがアンロックします。

コンポーネントを最適化する【別解】

2つのByte Splitterコンポーネント、8つの基本的な演算ゲート、合計10つのコンポーネントにまで最適化した回路です。

この回路だと「Condition 10」という実績を解除できます。