NANDゲートから始めるコンピュータ作り - Turing Complete プレイ感想

これまでNANDゲートからコンピュータを組み立てるという話になると、僕たちが真っ先に思い浮かべるのは nand2teris という神コースだった。このコースは、実際に動作するコンピュータ（エミュレータ上で動くもの）を作る方法を教えてくれる。

最も基礎的な理論から始まり、まずはハードウェア層の論理ゲートや各種回路設計の指示から必要なコンポーネントを自作し、アセンブリ言語や命令セットを設計し、最終的にはソフトウェア層のプログラミング言語を作成する。コンパイラやアセンブラまで網羅されている。基本的にnand2tetrisを一通り修了すれば、コンピュータが裏側で一体どのように動いているのかが分かるようになる。

チューリング完全

CPUの役割を分解してみると、その操作の大半が演算を行っていることが分かる。四則演算、ビットシフト、行列乗算などだ。では、あるコンピュータが「計算可能なすべてのもの」を計算できるかどうかは、どうやって知ればいいのだろうか？

例えば、ゲーム内では加算を行える全加算器（full adder）が登場するし、減算は補数の概念を使って加算で実現できる。では、乗算はどうだろう？sin関数は？cos関数は？

乗算器、sin演算器、cos演算器といった新しいハードウェア回路を際限なく追加していくこともできるが、それではキリがない。世の中にはあまりにも多くの数式が存在し、そのすべてをハードウェア回路で実装することなど不可能だからだ。

チューリングはその論文の中で「チューリング完全」という理論を提唱した。簡単に言えば、現在実行中の命令のアドレス（プログラムカウンタ）を保持し、現在の命令に基づいて次の状態（レジスタ）を得ることができれば、チューリング完全を達成できる。これは実に不思議なことであり、チューリングはこのような構造によって計算可能なすべての関数を解決できることを証明した。

デジタルロジックの視覚化

最近、steam で『Turing Complete』というゲームを見つけた。そのコンセプトはnand2tetrisと瓜二つ（ただしアセンブリ言語まで）で、論理ゲートから少しずつ組み立てていってチューリング完全なコンピュータを作るゲームだ。

このゲームは視覚化によってコードの記述をドラッグ＆ドロップ可能な論理ゲートに変え、リアルタイムなインタラクションによって真理値表の変化を観察しやすくしている。

配線を引くことで紙とペンで真理値表を書き写す手間を省き、マウスクリックで1と0（ONとOFF）を切り替えることで、ソフトウェアのインストールやHDL（ハードウェア記述言語）を省略し、プレイヤーができる限りコアな概念から始められるようになっている。

1つのCPUは無数のNANDゲートを組み合わせた回路へと分解できる。プレイヤーの目標は、論理ゲートから始めて一歩ずつステージをクリアし、最終的に動くコンピュータを1台作り上げることだ。

論理ゲートからレジスタ、メモリ、マルチプレクサ、デマルチプレクサなど様々な回路を組み合わせていき、各機能ごとの小さなステージを通じて回路の特性を理解していく。ステージをクリアすると、ゲームは自分で組んだ回路をコンポーネント化して提供してくれるため、ゲームが進むにつれてコンポーネントはどんどん増えていく。後半のステージの回路はますます複雑になり、必要なコンポーネントや配線も増えていく。

チューリング完全への道

ゲーム内での重要な分岐点はチューリング完全だ。「WORKING COMPUTER」をクリアしたとき、これまで苦労して組んできた回路はすべてこの瞬間のためのものだったのだと気づかされる。このステージでは、いくつかの条件を満たすことが求められる：

• バイトコードの bit に基づいて実行する操作（ADD、XOR、ORなど）を判断する
• Program Counter：プログラムがどこまで実行されたかを記録する
• 特定の bit に基づいて jump（指定したアドレスへのジャンプ）を実行するかどうかを判断する：6つのケース（大なり、小なり、等しい、always、never）を実装する必要がある
• 5つのレジスタ

このゲームの面白いところは、プレイヤーごとに引いた回路が完全に同一にはならず、それぞれの個性や実装方法が現れる点にある。

これを完成させれば、コンピュータに必要な機能は基本的に達成できたことになり、重要なマイルストーンとなる。しかし、ゲームはここで終わりではない。次は自分が組んだ回路を使って、ステージで指定された要件を達成することが求められる。例えば：

• mod 4 の計算：最初はバイトコードを手動でポチポチ入力させられる

  

• 2 * pi * r の計算：ここからはエディタで書けるようになり、自分で命令を名付けて独自の命令セットを作成できる

• 迷路脱出：コードを書いて迷路を攻略する

もし本当に自分の頭を使い、手を動かしてゲームのステージを最後までクリアすれば、コンピュータアーキテクチャの知識を数多く吸収できると思う。教科書を併用して理解を深めれば、一部のエンジニアよりも堅固な基礎を身につけられるかもしれない。

既存の回路をさらに進化させる

アセンブリ言語で指定のステージをクリアすると、次は既存のアーキテクチャにさらに高度な要素を加えていくことになる。単純な例を挙げると、なぜレジスタの数は限られているのに、プログラム内にはあんなにたくさんの変数が存在できるのか？その答えはRAMだ。そのためゲームは次に、RAMを追加してアドレッシングを行い、指定された機能を達成することを求めてくる。

元々の回路は命令を実行する際、r1、r2、r3 を計算用やジャンプ用のレジスタとして固定で使うしかなかった。しかしこれではコードの記述が面倒なため、ゲームは OPCODE、argument1、argument2、result というアーキテクチャの実装を求めてくる。プログラムは毎回4バイトを読み込み、プレイヤーはその4バイトをデコードして、引数にどのレジスタを使い、結果をどのレジスタに格納するかを回路全体で自由に決められるようにする。

RAMが備わり、より柔軟な回路アーキテクチャが整ったら、次はスタック機能の実装だ。これによって回路が一連のコンテキストを保存できるようになり、後の関数（function）実装の基礎となる。これは回路がさらに一段と複雑になることを意味している。

この段階に到達すると、新たな機能である「scoring（スコアリング）」がアンロックされる。回路を実装する際は、なるべく多くの操作を同時に行うのが理想的だ。回路が通過する論理ゲートが増えるほどディレイ（遅延）が大きくなるためだ。ゲームはNANDの使用数とディレイを計算してくれるので、回路を手直ししてより良いパフォーマンスを追求できる。

その後のステージの大部分は、既存のアーキテクチャに修正を加えながら、アセンブリ言語でさらに高度なミニゲームをクリアしていくことになる。

欠点

このゲームは現在まだ開発中であり、非常に強固なITの基礎知識は必要ないものの、論理ゲートが何をするものかをある程度理解し、2進数の概念を把握してからプレイした方が入りやすいかもしれない。

また、ゲーム内のガイダンスやヒントがあまりにも少なすぎる。多くの場合、時間をかけて悪戦苦闘し、試行錯誤と回路改善の思考を繰り返すことになる。特に後半になると回路がますます難しくなり、ゲームの楽しさを感じられなくなる場面も多い。UIもそれほど分かりやすいとは言えず、配線作業にかなり苦しめられた。

プレイ中にゲームが突然クラッシュすることが何度もあり、中盤から終盤にかけて非常に高い頻度で発生した。正式リリース後に改善されることを願っている。

ゲームをプレイして本当に学べるのか？

同様の例として、Nintendo Switchの『ナビつき！ つくってわかる はじめてゲームプログラミング』が挙げられる。

この作品のチュートリアル設計は非常に優れており、豊富な実例を用いて次にどんな機能を実装するのか、その実装には何が必要なのかを示し、実際に動かして結果を確認させ、修正を促してくれる。要件定義→実装→検証→修正という流れは、実際の開発サイクルと非常によく似ている。ゲーム内でコードを書く必要は一切なく、すべての機能は「ノード」として抽象化されており、ドラッグ＆ドロップでつないでいく。プログラミングの本質は決して構文そのものではなく、その背後にある思考ロジックだ。しかもNintendo Switchの『はじめてゲームプログラミング』のリファレンス（関数ドキュメント）は極めて秀逸で、開発者の手本と言ってもいいほどだ。

『Turing Complete』というゲームは少々マニアックで、手取り足取りのチュートリアルは基本的に存在しない（正式リリース後に追加されるかは分からない）。そのため、大半のことは自力で何とかしなければならない。

ゲーミフィケーションの利点は、不要な環境構築や設定、プログラミング言語の記号理解をすべて省略し、最もコアな概念へと直接飛び込めることだ。作者が論理ゲートや真理値表の概念を視覚化しドラッグ＆ドロップ可能なブロックとして抽象化したことで、コードやテキストを書くよりもはるかに直感的になっている。

感想

このゲームを通じて、コンピュータアーキテクチャの基礎を改めて振り返ることができたし、nand2tetrisの復習にもなった。以前学校で似たような授業を多少は受けていたものの、ゼロから自分の手で実際に動くコンピュータを作り上げるようなカリキュラムはごく稀だ。大部分のことは学校で習っていたとはいえ、実際に手を動かして配線するとやはり問題に直面しやすく、それだけに苦労して回路を組み上げたときの喜びはひとしおだった。

実際にはもちろん、ゲーム内で配線して組んだ回路をそのまま実用できるわけではないし、現実世界では単に機能を繋げば済むという話でもない。しかし入門学習としては、学習者がコアとなる概念をより素早く掴むのに大いに役立つ。コンピュータが裏でどのように動いているのか興味がある人には、ぜひおすすめしたいゲームだ。

トレイラー映像の中で、僕の心に強く残った言葉がある：

If you try to make such projects, unseen by others, as perfect as any human could, you’ll develop skills that other professionals don’t have

だが、クリアした後に感じたのは、このゲームの参入障壁はあまりにも高すぎるということだ。チュートリアルや説明が極めて少なく、内容も非常に難解で、最初から回路の実装を求められるため、2進数やデジタルロジックに不慣れなプレイヤーはあっという間に挫折してしまうだろう。後半のヒントや説明は無いに等しく、その難易度の高さから、行き詰まって頭を抱えるのはごく日常茶飯事だ。そのため、純粋な娯楽としてのゲームを期待して遊ぶのには向いていないかもしれない。

むしろ21世紀に入りコンピュータの発展がここまで成熟した現在、コンピュータの強力な演算能力と視覚効果は、学習効率を指数関数的に高めてくれるとさえ思う。デジタルロジックを学ぶ際、回路では入力の組み合わせと出力の関連性を観察するために、入力値を頻繁に変更したくなる。これを紙の上でやろうとすると消しゴムで数字を書き直す必要がありかなり面倒だが、コンピュータ上なら話は別だ。マウスクリックひとつで0から1へと切り替わり、出力もリアルタイムに変化する。

• フィードバックサイクルのコスト低下
• 結果をリアルタイムに観察可能

この2点だけでも、僕たちの学習効率は何十年も前の人たちを遥かに凌駕している。

参考

これは以前配信したライブ配信のアーカイブだ。ゲームの全内容を配信したわけではないが、大部分のステージはここで確認できるはずだ。