NANDロジックゲートからコンピュータを作る - Turing Completeゲームの感想

💡

質問やフィードバックがありましたら、フォームからお願いします

NANDロジックゲートを用いたコンピュータについて語るとき、最初に思い浮かぶのは、nand2tetrisという素晴らしいコースです。このコースでは、実際に動作するコンピュータを（エミュレーター上で）作成する方法を学びます。

基本的な理論から始まり、ハードウェアレベルのロジックゲートやさまざまな回路設計命令について学び、必要なコンポーネントを自分で作成し、アセンブリ言語と命令セットを設計します。最後には、ソフトウェアレベルのプログラミング言語を作成し、コンパイラやアセンブラに関する知識もカバーされます。基本的に、nand2tetrisを修了すれば、コンピュータがどのように動作するのか理解できるようになります。

チューリング完全性

CPUの動作を分解してみると、ほとんどの操作が計算を行っていることが分かります。加算、ビットシフト、行列の乗算など、では、すべての「計算可能なもの」を計算できるかどうかはどうやって判断するのでしょうか？

たとえば、ゲームの中で全加器（full adder）に遭遇します。これは加算操作を実行し、減算は補数の概念を用いて加算で行うことができます。では、乗算は？sin関数は？cos関数は？

新しいハードウェア回路（例：乗算器、sin関数器、cos関数器）を次々と追加することはできますが、無限に続くため、世の中には多くの公式が存在し、すべてをハードウェア回路で実現することは不可能です。

チューリングは彼の論文でチューリング完全性という理論を提唱しました。簡単に言うと、現在実行中の命令のアドレス（Program Counter）を保存し、現在の命令に基づいて次の状態（Register）を得ることができれば、チューリング完全性を達成できます。このことは実際に非常に驚くべきもので、チューリングはこのような構造がすべての計算可能な関数を解決できることを証明しました。

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

最近、steamでTuring Completeというゲームを見つけました。このゲームは、nand2tetrisと同様のコンセプト（ただしアセンブリ言語まで）を持ち、ロジックゲートから始めて徐々にチューリング完全なコンピュータを組み立てていきます。

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

XOR gate

ケーブルを引くことで、紙とペンで真理値表を手書きするコストを削減します。マウスをクリックして1と0（ONとOFF）を切り替え、ソフトウェアのインストールやHDL記述言語を省略し、プレイヤーがコアの概念から始めやすくしています。

CPUは無数のNANDロジックゲートで構成された回路に分解できます。あなたの目標は、ロジックゲートから始めて、段階的にレベルをクリアし、最終的に動作するコンピュータを作成することです。

ロジックゲートから様々な回路を組み合わせ、レジスタ、メモリ、マルチプレクサ、デマルチプレクサを含む様々な機能の小さなレベルを通じて回路の特性に慣れさせます。レベルをクリアすると、ゲームはあなたが組んだ回路をコンポーネントとして提供します。ゲームが進むにつれて、コンポーネントは増えていき、後半のレベルでは回路がますます複雑になり、必要なコンポーネントやケーブルも増えていきます。

full adder

demux

チューリング完全性への道

ゲームの中で重要な分岐点はチューリング完全性です。WORKING COMPUTERを完成させると、これまで苦労して組み立てた回路がこの瞬間のためであったことがわかります。このレベルでは、いくつかの条件を満たす必要があります：

バイトコードのビットに基づいて、どの操作を実行するかを判断する：ADD、XOR、ORなど
プログラムカウンタ：プログラムがどの位置で実行されているかを記録
特定のビットに基づいてジャンプ（指定されたアドレスに飛ぶ）するかどうかを判断する：6つのシナリオを実装（大きい、小さい、等しい、always、never）
5つのレジスタ

Turing Complete

このゲームの面白いところは、各プレイヤーが引き出した回路が完全に同じではなく、各自のスタイルと実装方法を持っている点です。

これを完了すると、実際にコンピュータに必要な機能を達成したことになります。重要なマイルストーンと言えるでしょう。しかし、ゲームはここで終わりではありません。次に、あなたが組んだ回路を使って、レベルが指定するニーズを満たすことが求められます。たとえば：

mod 4を計算する：ゲームの最初では、バイトコードを使って少しずつ進むよう指示されます。
2 * pi * rを計算する：次に、エディタを使用して自分で命令を書くことができます。命令に名前を付け、独自の命令セットを作成できます。

assembly editor

迷路を歩く：プログラムコードを記述して迷路を進む。

実際に頭を使って、手を動かしてゲームのレベルをクリアすれば、コンピュータの組織に関する知識を多く吸収できると思います。教科書と組み合わせれば、特定のエンジニアの基礎よりも堅実な理解が得られるかもしれません。

既存の回路を進化させる

一旦、アセンブリ言語で指定されたレベルをクリアすると、次に既存の構造にさらに高度なものを追加します。簡単な例として、なぜレジスタの数が限られているのに、プログラム内にはそれほど多くの変数が存在できるのでしょうか？その答えはRAMです。次に、ゲームはRAMを追加し、アドレッシングを行い、指定された機能を達成することを求めます。

RAM

元々の回路は、命令を実行する際にr1、r2、r3を計算やジャンプ用のレジスタとして固定的に使用するだけですが、これではプログラムコードを書くのが煩雑です。そこで、ゲームはOPCODE、argument1、argument2、resultという構造を実装するよう求めます。プログラムは毎回4バイトを読み取り、4バイトをデコードして、全体の回路がどのレジスタを使用するか、結果をどのレジスタに保存するか自由に決定できるようにします。

RAMが加わることで、より柔軟な回路構造が実現され、次はスタック機能を実装します。これにより、回路は一連のコンテキストを保存できるようになり、後に関数を実装するための基礎となります。これにより、回路はさらに複雑になります。

Stack circuit

この段階に達すると、新しい機能—スコアリングがアンロックされます。回路を実装する際、理想は同時にできるだけ多くの操作を行うことです。なぜなら、回路がより多くのロジックゲートを通過するほど、遅延が増えるからです。ゲームはあなたのNAND使用数と遅延を計算し、回路を改良するために戻って変更できるようにします。

次のレベルのほとんどは、既存の構造を修正し、アセンブリ言語を使ってさらに高度なミニゲームを完成させることです。

欠点

このゲームは現在開発中で、非常に堅実なIT基礎が必要というわけではありませんが、ロジックゲートが何をしているのかを理解しておく必要があります。二進数の概念があると、より簡単に遊ぶことができます。

さらに、ゲーム内のガイドやヒントは非常に少ないため、時間をかけて試行錯誤し続ける必要があります。特に後半になると回路がますます難しくなり、ゲームの楽しさを体験できないことが多いです。ゲームインターフェースもあまり理解しやすくなく、ケーブルを引くのが非常に困難です。

ゲームの途中で突然クラッシュすることが何度もあり、特にゲームの後半で発生頻度が非常に高かったです。正式版リリース後に改善されるかどうかは不明です。

ゲームを遊ぶことで本当に学べるのか？

同様の例として、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

しかし、遊んだ後、このゲームの習得の難易度が非常に高いと感じました。ゲームの教育と説明が非常に少なく、非常に難解なため、最初から回路を実装することは、二進数やデジタルロジックに不慣れなプレイヤーにとっては非常に難しいです。後半のヒントや説明はほぼないに等しく、難易度の関係から、行き詰まりや思考に没頭することが非常に普通です。そのため、純粋なエンターテイメントとして楽しむのにはあまり向いていないかもしれません。

21世紀のコンピュータの発展が非常に成熟し、コンピュータの強力な計算能力と視覚化効果が学習を指数関数的に助けることができると私は考えています。デジタルロジックを学ぶ際、回路上では入力の組み合わせと出力の関連を観察したいと思うことが多いため、入力値を変更し続ける必要があります。これを紙で行うのは非常に面倒です。なぜなら、消しゴムで数字を修正しなければならないからですが、コンピュータ上では異なります。マウスを一度クリックするだけで0が1に変わり、出力も即座に変化します。