ミジンコによるTuring Complete攻略

2023年9月12日2024年3月22日

Turing Completeとは

Turing CompleteはCPUアーキテクチャーを学べるパズルゲームです。自作CPUに興味を持っている初心者に最適でしょう。

NANDゲートから始まり、段々と複雑な回路を作り上げて、最終的に4ビットCPUができあがります。そして、そのCPU専用のマシン語を実装し、アセンブリー言語でのプログラミングを体験します。

Steamで約2,000円で販売されています。セールのタイミングで安くなることがあります。

Turing Completeの特徴

• キャンペーンに用意されたステージを段階を追ってクリアすることで、「デジタル回路⇒CPU設計⇒アセンブリー言語」の順で習得できる。
• 序盤は比較的簡単だが、中盤からはデジタル回路初心者にとっては厳しいかもしれない。
• 前提知識があれば、2週間ほど全ステージをクリアできるかもしれない。
  • 私はすべての攻略記事を書きながらだったので、約1.5ヶ月かかった。
• サンドボックスモードで、ステージ関係なく自由に回路を組める。
• 作った回路を投稿することもできる。
• 大幅アップデートにより、一部のステージが変更になる可能性がある。
  • 過去にもそういったことがあった。

得られるスキル

• デジタル回路の基礎･･･FFやシフトレジスターの実装はあるが、それ以上突っ込むことはない。デジタル回路の本で例えると、前半3分の1ぐらいの基礎が身につく。シミュレーター上で完結するので、リアルの世界にある泥臭いテクニックは不要（逆に習得できない）。
• 自作CPU･･･4バイト命令のCPUが完成する。複雑な命令はないので、理解しやすい。
• アセンブリー言語･･･レジスター、条件分岐、スタック、RAMといった基本的なプログラミングスキルは身につく。ハンドアセンブルを体験できるのはよい。たただし、フラグレジスターがないので、リアルなCPUのアセンブリー言語のプログラミングテクニックは扱わない。

ミジンコがTuring Completeを紹介した場面

『ホワイトハッカーの教科書』

『ホワイトハッカーの教科書』のP.154で紹介。遊びながら学べるゲームを4つ紹介したが、その1つがTuring Completeである。

「第100回 ゆるいハッキング大会」

「ミジンコがTuring CompleteでCPUを自作した話」と題して発表しました。

ステージ構成【2023年版】

各ステージの攻略記事

キャンペーンでは次のステージが用意されています。

下から上のステージに進んでいます。

1. Basic Logicカテゴリー

ステージNo.	ステージ名	内容
1.1	Crude Awakening
1.2	NAND Gate
1.3	NOT Gate
1.4.1	AND Gate
1.4.2	NOR Gate
1.4.3	OR Gate
1.5	Always ON
1.6	Second Tick
1.7	XOR Gate
1.8.1	Bigger OR Gate
1.8.2	Bigger AND Gate
1.9	XNOR Gate

2. ArithmeticカテゴリーとMemoryカテゴリー

左右に分割されています

ステージNo.	ステージ名	内容
2.1.1	Binary Racer
2.1.2	Double Trouble
2.1.3	Odd Number of Signals
2.1.4	Circular Dependency
2.2.1	Counting Signals
2.2.2	Half Adder
2.2.3	Delayed Lines
2.3.1	Double the Number
2.3.2	Full Adder
2.3.3	Odd Ticks
2.4.1	Bit Switch
2.4.2	Bit Inverter
2.5.1	Byte OR
2.5.2	Byte NOT
2.5.3	Adding Bytes
2.6.1	Negative Numbers
2.6.2	Input Selector
2.7.1	Signed Negator
2.7.2	The Bus
2.7.3	Saving Gracefully
2.8	Saving Bytes
2.9	1 Bit Decoder
2.10	3 Bit Decoder
2.11.1	Logic Engine
2.11.2	Little Box
2.11.3	Counter

3. CPU Architectureカテゴリー

ステージNo.	ステージ名	内容
3.1.1	Arithmetic Engine
3.1.2	Registers
3.2	Component Factory
3.3	Instruction Decoder
3.4	Calculations
3.5.1	Conditions
2.5.2	Program
2.6	Immediate Values
2.7	Turing Complete

4. Programmingカテゴリー

ステージNo.	ステージ名	内容
4.1	Add 5
4.2	Calibrating Laser Cannons
4.3.1	Spacial Invasion
4.3.2	Storage Cracker
4.3.3	Masking Time
4.4	The Maze

5. CPU Architecture 2カテゴリー

ステージNo.	ステージ名	内容
5.1.1	XOR
5.1.2	Byte Constant
5.2.1	Byte XOR
5.2.2	Equality
5.3.1	Unsigned Less
5.3.2	Signed Less
5.4	Wide Instructions
5.5	Wire Spaghetti
5.6	Opcodes
5.7	Immediate Values
5.8	Conditionals

6. Functionsカテゴリー

ステージNo.	ステージ名	内容
6.1.1	Hex Racer
6.1.2	Shift
6.1.3	RAM
6.1.4	Delay
6.2.1	The Product of Nibbles
6.2.2	Stack
6.2.3	The Lab
6.3.1	Divide
6.3.2	PUSH and POP
6.4	Functions

7. Assembly Challengesカテゴリー

ステージNo.	ステージ名	内容
7.1.1	AI Showdown
7.1.2	Robot Racing
7.1.3	Unseen Fruit
7.1.4	Delicious Order
7.2.1	Dancing Machine
7.2.2	Tower of Alloy
7.2.3	Planet Names
7.3	Water World

全実績解除を目指す

Turing Completeには実績（Achivement）が用意されています。ストーリーモードを全クリアしたら、力試しに全実績の解除を目指すのはどうでしょうか。

難易度はグローバル実績の達成割合から推定しました。

※アップデートによって実績が増減する可能性があります。

実績名	実績解除の条件
Turing Complete	Turing Completeステージをクリアする。
5 Component Full Adder	5つの青いコンポーネントだけを使って、Full Adder回路を作成する。 Full Adderステージの解答で実績解除できる。
4 NAND = XOR	4つのNANDコンポーネントのみを使ってXOR回路を作成する。 XORステージの別解3で実績解除できる。
Symmetric ALU	8ビット用コンポーネントのみを使ってLogic Engine回路を作成する。 Byte Splitterコンポーネントは8ビット用コンポーネントなのでセーフだが、3 Bit Decoderコンポーネントは使えない。 Logic Engineステージの別解などで実績解除できる。
3 Adder Multiply	3つを超える8ビット加算器を使わずに（3つはセーフ）、The Product of Nibblesステージを解く。 The Product of Nibblesステージの別解で実績解除できる。 別解は3つの8 Bit Full Adderコンポーネントを使っているのでセーフである。
Tutorial Complete	Functionsステージをクリアする。 このステージをクリアすると、記念すべき1つ目のCPUが完成したことになる。
Condition 10	10つの青いコンポーネントだけを使って、Conditionsステージをクリアする。 Conditionsステージの別解で実績解除できる。
Fast Adder	遅延スコア35以下のByte Adder回路を完成させる。 Adding Bytesステージの別解4で実績解除できる。
Water world	最終ステージであるWater Worldステージをクリアする。
Binary Counter	CounterステージをNANDスコア65以下でクリアする。 Counterステージの別解2で実績解除できる。
FastBot	64バイト以下のコードでRobot Raceステージをクリアする。 Robot Raceステージの別解3で実績解除できる。
Helperbot	宇宙船の4クエストをすべて完了する。 The Mazeステージをクリアすると迷路の外に出て、4つのクエストすべてにアクセスできるようになる。 攻略記事はこちらから。
Best hat	【隠し実績】伝説の最高の帽子を入手する。 攻略記事はこちらから。
Black hat	【隠し実績】帽子売りをハックする。 攻略記事はこちらから。
Binary Racer	【隠し実績】Binary Racerステージで最終レベル（レベル7）をクリアする。 攻略記事はこちらから。 現在、人間には現実的な不可能なレベルといわれている。

Turing Complete
最後に残っていた実績「Binary Racer」（解除率0.6%）をクリア。これで全実績を解除😀https://t.co/ey2uhSDu3B pic.twitter.com/NkySx95jTz

— IPUSIRON (@ipusiron) November 1, 2023

ミジンコのプロフィールデータ