Turing Complete 解答一覧 (Ver. 0.1028Beta)

Turing Completeの解答と簡単な解説を入れた日本語ガイドです。2022日10月03日 Ver. 0.1028Betaに対応完了しました

SPOILER ネタバレ注意

このガイドでは各問題の答えとなる画像を貼り付けています。spoilerタグで画像を隠す方法もあったのですが、使い勝手が悪かったのでそのままにしています。自力で解いてこそ楽しめる作品だと思いますが、どうしても詰まってしまった、答えを知りたいという場合にご利用ください。

書いていたらなんか参考書チックになってしまったので、勉強みたいでやだなーと思ったら無理して読まなくてOK。分かる範囲で楽しめりゃいいんだよ(ﾟ∀ﾟ)

あと、わかりやすさを重視して、NANDの数が最小になる構成を突き詰めていません。その点ご了承ください。

1. Basic Logic

---

1-1. Crude Awakening
操作説明。画面左上のINPUTをクリックするとON/OFFを切り替えて動作確認できる。

---

1-2. NAND Gate
NAND素子の動作確認。動作確認をしながら下の表を埋めればクリア。この素子ひとつで他のすべてを作ることになる。

---

1-3. NOT Gate
1-4-1. AND Gate
1-4-2. NOR Gate
1-4-3. OR Gate
1-5. Always On 常時ONを出力する素子を作る問題。
1-6. Second Tick Input1がON、Input2がOFFのときのみONを出力させる問題。

---

1-7. XOR Gate

解説
解法2はNANDが少なく低遅延な構成(実績あり)。ORで2つ、ANDで2つNANDを経由していたのに比べて、3つのNANDを経由するだけで出力できるので、遅延が少ない。

---

1-8-1. Bigger OR Gate
1-8-2. Bigger AND Gate
1-9. XNOR Gate

2. Arithmetic

---

2-1-1. Binary Racer
10進数で出された数字を2進数で答える練習ステージ。

---

2-1-2. Double Trouble
4つの入力のうち2つ以上がONになっているときにONを出力させる問題。
2-1-3. ODD Number of Signals
奇数判定の問題。4つの入力のうち奇数個がONになっているときにONを出力させる。

解説
XORのXORをとればよい。表にするとわかりやすい。

0000 -> 00 -> 0
0001 -> 01 -> 1
0010 -> 01 -> 1
0011 -> 00 -> 0
...

2-2-1. Counting Signals 4つの入力のうちONになっている個数を2進数で出力させる問題。

解説
さっきの奇数判別の回路を流用できる。
・1の位は奇数判定の回路と同じ。
・2の位は、1,2と3,4の両方のXORがONのとき、1,2と3,4のうち片方のANDがONのとき、の2パターン考えられるので、それをORでつなげばいい。

確認できるパターン
2個がON: 1010, 1001, 0110, 0101 -> XORを2つとANDで確認
2個がON: 1100, 0011 -> ANDを2つとXORで確認
3個がON: 1110, 1101, 1011, 0111 -> ANDを2つとXORで確認

・4の位はすべてがONのときにONを出力するようにAND回路を組めばいい。

2-3-1. Double the Number 1byteの入力を倍にして出力する問題。

解説
1bitずらせば、1が2に、2が4に、4が8に...という具合にすべての桁を2倍にできる。

---

2-2-2. Half Adder
半加算器を作る問題。論理回路の問題では必ずと言っていいほど出てくる半加算器。2進数の1桁の足し算の計算結果を出力しよう。

解説
1の位は片方がONのときにONになるのでXOR、2の位は両方がONのときにONになるのでANDを使うといい。表にするとわかりやすい。

00 -> 0,0
01 -> 1,0
10 -> 1,0
11 -> 0,1

2-3-2. Full Adder
全加算器を作る問題。半加算器にさらに繰り上がりを足すのを含めたもの。3つの入力の合計を2進数で出力するのが目的。

最大でも全部が1のときに11(つまり3)を出力するのみなので出力は2桁になる。後の問題で出てくるが、繰り上がりを上の桁の計算に入れるように連結することで、桁数の多い足し算ができるようになる。

解説
半加算器を2つ組み合わせて実現する。2つの数字を半加算器に入れて2桁の出力を出した後、下の桁と3つめの数字をさらに半加算器に入れる。

最初の加算では00・01・10のパターンしかないので、繰り上がりが両方1になることはない。そのため、どちらかの加算で繰り上がりが出ていれば繰り上がりを1にすればいい。つまりORで繋ぐ。

0 0 0 -> 00 0 -> 00
0 0 1 -> 00 1 -> 01
0 1 0 -> 01 0 -> 01
0 1 1 -> 01 1 -> 10
1 0 0 -> 01 0 -> 01
1 0 1 -> 01 1 -> 10
1 1 0 -> 10 0 -> 10
1 1 1 -> 10 1 -> 11

---

2-4-1. Byte OR
2-4-2. Byte NOT
2-4-3. Adding Byte

---

2-5. Negative Numbers
負の数の概念が出てくる。
最上位ビットを-128とおけばうまくいくことが問題で説明されている。

---

2-6. Signed Negator
符号を反転させて、正の数を負の数に、負の数を正の数に変換する問題。



結論だけ書くと、Byte NOTで反転させて、1を足せばいい。
例えば、4を-4に変換するには、00000100 を 11111011 にして1を足すと 11111100 となる。

---

2-7. 1 bit decoder
INがOFFのときに上の出力をON、INがONのときに下の出力をONにする問題。

解説
0,1の信号を、0のときに1になる線と、1のときに1になる線に分ける回路。
これを作るの自体は簡単だが、のちに大きい回路を作るときに役に立つ。

---

2-8. 3 bit decoder
2進数の入力を分解する問題。1が入力されたときに1番目の端子をONに、8が入力されたときに8番目の端子をONにしよう。

解説
3つの端子を持つANDを使って力押してで解ける。さっきのDemuxを使って、各bitが0と1それぞれのときに別の線に出力させて、000のとき、001のとき、010のとき...と計8種類、各場合をAND回路で拾っていけば簡単だ。

---

2-9. Logic Engine
演算装置を作る問題。

解説
Byte ANDがなかっため、byte NOTとbyte ORを組み合わせてANDを作っている。NOR・NANDはOR・ANDにそれぞれNOTを通したもの。

3. Memory

---

3-1. Circular Dependency
自己参照・循環参照を作る問題。

解説
自己参照・循環参照を起こすと信号が高速で切り替わって回路が焼ききれてしまう場合があるので、通常のステージでは禁止されている。
上の例で言うと、NOTの手前がOFFなのでONを出力する、すると手前もONになるのでOFFを出力する、すると...と瞬間的に高速にON・OFFが切り替わって破損する。

---

3-2. Delayed Lines
信号を2tick遅らせる回路を組む問題。
3-3. Odd Ticks
1tickおきにON信号を出力する回路を組む問題。

---

3-4-1. Bit Switch
3-4-2. Bit Inverter
3-5. Input Selector
3-6-1. The bus

---

3-6-2. Saving Gracefully

---

3-7. Saving Bytes

---

3-8-1. Little Box
1byteの情報を格納する2bitのメモリを作る問題。
SAVE・LOADの信号と、A1・A2・B1・B2のアドレスを指定する信号が入力されるので、4つの1bitメモリを用意して、ANDゲートを使って各1bitメモリにSAVE・LOADの信号を送る。
見た目は複雑だが、やっている事自体はシンプル。

---

3-8-2. Counter
プログラムカウンタを作る問題。

4. CPU Architecture

---

4-1-1. Arithmetic Engine
ALU(演算装置)を組むステージ。2-9のLogic EngineにADD(加算)・SUB(減算)を付け加えるとよい。

---

4-1-2. Registers
Copy命令を実装して、CPUの基礎を作る問題。

解説
CPUを作ると聞くと厳ついイメージがあるが、やることは割と単純。レジストリ(1byteのメモリ)のSave・Loadを操作して、レジストリどうしや入出力端子の間を数値を移動させる。
まずは各入力と出力をぐるっと繋ぐ。次に命令コードを1bitの信号に分解、各レジストリのSaveとLoad・入出力のONとOFFに繋げばそれで完成。配線もシンプル。

---

4-2. Component Factory
自由な素子を作れるサンドボックスのステージ。解くべき問題は用意されておらず、そのまま先に進める。

---

4-3. Instruction Decoder

---

4-4. Calculations
命令の上位2bitでComputeが指示されたときに、REG1とREG2の数値に対して2bitで指定された演算をして、REG3に結果を格納する。

解説
ALU(上の「4-2-1. Arithmetic Engine」で作った計算回路)に1byteの命令とREG1とREG2の常時出力を常に繋いでおき、Compute命令が出たときに結果をREG3に流し、REG3にSaveさせる。信号が混戦しないように注意しよう。

---

4-5-1. Conditions

解説
デコーダーで分解した8つの信号ごとに、ANDゲートで条件を満たすか確認し、それをORゲートでまとめている。Valueの入力から「=0」「!=0」「Negative(<0)」「Positive(>=0)」の情報を引き出し、その組み合わせで判定するかたち。

000 Never --- 接続しない
001 If value = 0 --- =0
010 If value < 0 --- Netagtive
011 If value <= 0 --- Netative or =0
100 Always --- そのままORに接続
101 If value != 0 --- !=0
110 If value >= 0 --- Positive
111 If value > 0 --- Positive and !=0

---

4-5-2. Program
プログラムメモリと、プログラムカウンタを実装するステージ。

---

4-6. Immediate Value

---

4-7. Turing Complete

5. Programming

---

5-1. Masking Time

CPUを作って終わりではない。ここからは実際に動かすことになる。
この問題では、Inputからの入力を4で割った余りを出力するのが目標。

プログラムメモリの右上のEditボタン(鉛筆マーク)で命令を編集できる。ダイアログ下側のInstructionsを押すと、どのbitをONにすればどんな命令になるか確認できる。

10 110 001 (Copy Input Reg1)
00 000 101 (Immediate 5)
10 000 010 (Copy Reg0 Reg2)
01 000 100 (Compute ADD)
10 011 110 (Copy Reg3 Output)

解説
入力に5を足すプログラム。上の5行で処理できる。上で設計したように、Immediate命令の数値はREG0に格納され、Compute命令はREG1とREG2の数値の演算結果をREG3に格納する。うまくCopy命令をつかって数値を移動させよう。

---

5-2. Calibrating Laser Cannon

隕石の半径から円周の長さを求める問題。π=3で計算していいということで、2πr=6r、つまりInputの入力を6倍にして出力すればいい。

今回からは右のようなダイアログで、バイトコードに1対1で命令を割り当てて、それを使ってコードを書くことができる。自分で使いやすい名前を割り当てよう。

今回使っている命令はこんな具合だ
reg1_to_reg2 は Copy Reg1 Reg2
in_to_reg1 は Copy Input Reg1
reg3_to_out は Copy Reg3 Output
add は Compute ADD

---

5-3-1. Special Invasion

今度はロボットを動かしてスペースインベーダーのようなことをする問題。ロボットの動かし方については右のような解説が追加される。

0～6の数字の出力で前後移動と左右への方向転換・足踏み・前方のオブジェクトの検知・レーザーの発射ができるほか、矢印キーやスペース,Ctrlなどで動作を試すこともできる。レーザーでインベーダーのように動く16体の宇宙ネズミを倒そう。

なお、レーザーは画面上に既にある場合、追加で発射することができない。

解説
Condition命令のお試し問題と言ってもいい内容。上で設計した通り、ConditionはReg3の数値を判定して、成立していればReg0の値をプログラムカウンタにコピーするので、Immediate命令で予めReg0にジャンプ先の行数を入れておくとよい。

また、Outputに直接好きな数字を送ることができないため、一旦Immediate命令でReg0に数字を入れ、Reg0からOutputにCopyしている。

インベーダー宇宙ネズミどもを倒すのに今回取った手順だが、
1. 最初に目の前の壁をぶち壊して一歩前に出る
2. 目の前を探索して入力を得て、0(なにもない)ならその場でループする
3. 0でないならレーザーを4回撃つ
こういう作戦だ。

---

5-3-2. Storage Cracker

解説
パスワードを解析するプログラムを作る問題。手法はシンプル、正解が見つかるまで0～9999のすべての数字を出力すればよい。簡単なループで解ける。
今回は「label」を使っている。行番号にラベル名をつけると、そのラベル名は行番号と同じ扱いがされる。

---

5-3-3. Masking Time

解説
入力を4で割った余りを出力する問題。このCPUに除算は実装されていないが、AND演算をすることで目的を達成できる。

---

5-4. The Maze
プログラムの題材としてはお決まりの、迷路を探索する問題。上下左右への方向転換と、前方のマスの判定を利用して左上のゴールに辿り着こう。

解説
この手の問題ではおなじみの、左手伝いに辿ればゴールに辿り着く法則を使う。
1. 前方を調べて、壁ならば、その場で右に方向転換して1.を繰り返す
2. 壁でなければ前進して左に方向転換
3. 1に戻る
この手順で実行できる。

6. CPU Architecture 2

---

6-1-1. XOR

---

6-1-2. Byte Constant
6-2-1. Byte XOR
6-2-2. Equality
6-3-1. Unsigned Less
6-3-2. Signed Less
6-4. Wide instructions



謝辞「6-3-2. Signed Less」の解答は、Edward_shooterさんの提案によるものです。感謝！

---

6-5. Wire Spaghetti

---

6-6. Opcodes

---

6-7. Immediate Values

---

6-8. Conditionals

7. Functions

---

7-1-1. Hex Racer
16進数の理解を確認するクイズステージ。

---

7-1-2. Shift
ビットシフト回路を組むステージ。

---

7-1-3. RAM
RAMを回路に組み込むステージ。

解説
空いているOPCODEにRAM_SAVEとRAM_LOADを割り当てる。今回は、問題文で示唆されているとおり、アドレス指定レジスタとして、REG5の値を参照するようにした。

また、RAM_LOADのときにレジスタへの書き込みが発生しないように、回路左上に書き込みを制限する回路を追加している。今後も同様のことが起こらないように、特定のOPCODEでのみレジスタへの書き込みを許可するようにしてみた。

---

7-1-4. Delay

解説
NAND SCOREとDELAY SCOREの解説のためのステージ。適当に配置して繋ぐだけでいい。
NAND SCOREは使用したNANDの数。DELAY SCOREは、コンポーネントごとの遅延を評価するためのもの。通過したNAND1つにつき2増える。

---

7-2-1. The Product of Nibbles
乗算回路を組むステージ。

---

7-2-2. Stack
スタックモジュールを組むステージ。

---

7-3-1. Divide
除算処理をするステージ。ここでは最も単純な除算アルゴリズムを用いて、ソフトウェア的に処理した。

解説
被除数から除数を1回ずつ引いていき、引いた回数を出力する単純なプログラム。商が大きくなると計算に時間がかかる。

---

7-3-2. PUSH and POP
スタックを回路に組み込むステージ。

---

7-4. Functions
関数呼び出しを実装するステージ。追加で、後の問題で必要になるビットシフト回路も実装してみた。

解説
このステージでは関数...というかサブルーチンの呼び出し「CALL」と、呼び出し元のアドレスに戻る「RET」の実装をする。関数からさらに関数を呼び出す際に、呼び出し元のアドレスを上書きしないように専用のスタックを使って戻り先アドレスを記録する。

「CALL」命令では引数を1つとり、専用スタックにプログラムカウンタの値を保存し、引数で指定されたアドレスでプログラムカウンタを上書きする。
「RET」命令では引数をとらず、専用スタックに保存されたカウンタの値+4でプログラムカウンタを上書きする。

今回は専用スタックの追加だけでなく、プログラムカウンタを上書きするための回路も追加している。

32bit CPU Instruction Set

レジスタ
00000000 REG0
00000001 REG1
00000010 REG2
00000011 REG3
00000100 REG4
00000101 RAM_ADDRESS
00000110 P_COUNTER
00000111 INPUT
00000111 OUTPUT

OPCODE
00000000 ADD (reg reg reg)
01000000 ADDi (reg value reg)
11000000 ADDii (value value reg)
00000001 SUB (reg reg reg)
01000001 SUBi (reg value reg)
11000001 SUBii (value value reg)
00000010 AND (reg reg reg)
01000010 ANDi (reg value reg)
00000011 OR (reg reg reg)
01000011 ORi (reg value reg)
00000100 NOT (reg _ reg)
00000101 XOR (reg reg reg)
01000101 XORi (reg value reg)
00000110 SHL (reg reg reg)
01000110 SHLi (reg value reg)
00000111 SHR (reg reg reg)
01000111 SHRi (reg value reg)

00100000 IF_EQUAL (reg reg address)
01100000 IF_EQUALi (reg value address)
00100001 IF_NOT_EQ (reg reg address)
01100001 IF_NOT_EQi (reg value address)
00100010 IF_LESS (reg reg address)
01100010 IF_LESSi (reg value address)
00100011 IF_LESS_EQ (reg reg address)
01100011 IF_LESS_EQi (reg value address)
00100100 IF_GT (reg reg address)
01100100 IF_GTi (reg value address)
00100101 IF_GT_EQ (reg reg address)
01100101 IF_GT_EQi (reg value address)

00101000 RAM_LOAD (_ _ reg)
00101001 RAM_SAVE (reg _ _)
00101010 POP (_ _ reg)
00101011 PUSH (reg _ _)

00101101 CALL (label _ _)
00101100 RET (_ _ _)

immediateBを使う場合に接尾辞「i」を、immediateA,Bを両方使う場合に接尾辞「ii」を付けている。

各命令の引数を使用しない箇所にはアンダースコア「_」を使っている。
div・modは除算回路を実装した場合のみ使用。

コードを読みやすくしつつ指定ミスをなくすために命名規則を決めてある。
命令は小文字のみ、
constによるレジストリの命名には小文字と2単語目以降の頭文字のみを大文字に、
constによる定数の命名には大文字とアンダースコアのみ、
ラベルの命名には1単語目から頭文字を大文字に、
などと決めておくと便利。

8. Assembly Challenges

---

8-1-1. AI Showdown
12枚の中から交互に1枚～3枚のカード引き、最後の1枚を引いたほうが負けというゲームを相手のロボットであるNAK 02と繰り広げる問題。

解説
よく考えるととても単純な計算式で対応できる。

引くカードの数 = (残りのカードの数 - 1) mod 4

理屈を説明すると、
1) 相手が1枚引いたときに3枚・2枚引いたときに2枚・3枚引いたときに1枚引くようにすると、1巡ごとに4枚のカードが減るように調整できる
2) 相手に最後の1枚を引かせるためには、相手のターンに「4の倍数+1」のカードが残るようにすればいい
3) 自分の手番で引くカードは、「残りのカードの数 - (4の倍数 + 1)」枚
4) 整理すると、「(残りのカードの数 - 1) を4で割った余り」の枚数を引けばよい

例えば12枚なら3枚引いて9枚に、ここから相手が3枚引いて6枚になれば、1枚引いて5枚にする。これを繰り返せば、相手は確実に最後の1枚を引くことになる。カードの枚数が4の倍数+1枚でない限り先手が勝つゲームとも言える。

Edward_shooter氏による、よりシンプルな別解
https://steamcommunity.com/sharedfiles/filedetails/?id=2870251109

---

8-1-2. Robot Racing

解説
反復するパターンが掴みにくい問題。この迷路はフラクタルな空間充填曲線であるヒルベルト曲線と呼ばれるもの。正方形をコの字型に4つの領域に分割し、それぞれの領域をさらにコの字型に分割していくことで作られる。再帰的に処理することで、短いプログラムで移動指示を出すことができる。

再帰的に処理する際にコの字の向きと裏表を変える必要があるのだが、XORを重ねて使うことでうまく処理できる。

別解:
クリアするだけなら、すべての行動をプログラム上に書きあげるハードコーディングの力技でも解決できる。

---

8-1-3. Unseen Fruit
コンベアを流れてくるフルーツを記録して、同じフルーツが2つ以上流れてくると報告する問題。

解説
RAMを活用する練習問題。流れてきたフルーツのIDをRAMに記録し、記録されたフルーツと比較して同じものがあれば報告する。

---

8-1-4. Delicious Order
ソート問題。

解説
基本的な選択ソートで実装してみた。ソートアルゴリズムはネット上の各所に解説があるので割愛。

---

8-2-1. Dancing Machine

解説
擬似乱数生成器を組む問題。問題文に書かれている通りのアルゴリズムを実装するだけなので、特に難しい問題ではない。擬似乱数の生成についても深堀りすると楽しいはず。

---

8-2-2. Tower of Alloy
ハノイの塔を解く問題。問題文に表示されているとおりのアルゴリズムを実装すればよい。

解説
再帰関数を使う問題。「7-5. Functions」で実装したcallとretを活用する。この解法では、元の階層の変数の値を汎用スタックに詰め込んでみた。

---

8-2-3. Planet Names
スペースで区切られた各単語の頭文字1文字を大文字に変換して出力する問題。

---

8-3. Water World

[Andrei030x]

2-6. Signed Negator
あなたの計画は不公平です。 コンパクトに見えます。 しかし、「ADD」コンポーネントのトランジスタの数を考慮すると、それは非常に不器用です。
あなたの計画 では136NANDゲート。 私の計画 では34NANDゲート。私の決定は4倍優れています。

[jychoi9002]

wire spagetti I did same as you but doesn't work....exactly same.

[masterdisasterHD]

@Nex

this is my solution for push and pop:
-----------------------------------------------------------
const disk REG0

label main
ADDi INPUT 0 disk
IF_EQUALi disk 0 pop
IF_NOT_EQi disk 0 push
CALL main _ _

label push
PUSH disk _ _
ANDi disk 0 disk
IF_EQUAL 0 0 main # always return to main

label pop
POP _ _ disk
ADDi disk 0 OUTPUT
IF_EQUAL 0 0 main # always return to main
---------------------------------------------------------

[Nex]

Would someone be able to help me out on the push and pop program?

[Nex]

I was stuck on the RAM section for a while, if anyone needs some WORKING CODE:
------------------------------------------------
label loop
ADDi RAM_ADDRESS 1 RAM_ADDRESS
RAM_SAVE INPUT _ _
ADDi REG0 1 REG0
IF_LESS_EQi REG0 32 loop

SUB RAM_ADDRESS RAM_ADDRESS RAM_ADDRESS
SUB REG0 REG0 REG0

label read
ADDi RAM_ADDRESS 1 RAM_ADDRESS
RAM_LOAD _ _ OUTPUT
ADDi REG0 1 REG0
IF_LESS_EQi REG0 32 read

------------------------------------------
REQUIREMENTS:
- Make sure that it is built properly
- Make sure that all your Asembly codes MATCH the 32bit CPU instruction set
- Add a new Assebly code as followed: '00000000' named as '_'

NOTE: This worked for ME following the same Diagram as depicted on the RAM level. It might NOT work for you. This is also probably poor design and falued but idc. Enjoy.

[qhliu12138]

こんにちは、Steamでチューリング完備攻略についての投稿を見ました。特にRAMのパートについて質問があり、対応するコードを共有していただくか、説明を教えていただけないでしょうか？このチャレンジに非常に興味を持っており、より深く理解したいと考えています。お手数をおかけしますが、よろしくお願いします。

[Edward_shooter]

@Hollyleaf 2-1-2. Double Trouble
https://steamcommunity.com/sharedfiles/filedetails/?id=2929885231

[Edward_shooter]

7-3-1. Divide:

Division is possible using only hardware, with the designs from my Reddit post:
https://www.reddit.com/r/TuringComplete/comments/xt817z/divide_but_without_looping/

My solution: (unoptimized)
https://preview.redd.it/xushx2mis9r91.jpg?width=1707&format=pjpg&auto=webp&v=enabled&s=2c60f69718ea88d4bfcc2aa4c30321641c6638fa

FatTomIV's solution: (optimized)
https://i.imgur.com/JOGK8g7.png

Sorry for not telling you earlier, I forgot to.



私のReddit投稿からの設計により、ハードウェアのみを使用して分割が可能です。
https://www.reddit.com/r/TuringComplete/comments/xt817z/divide_but_without_looping/

私の解決策：（最適化されていません）
https://preview.redd.it/xushx2mis9r91.jpg?width=1707&format=pjpg&auto=webp&v=enabled&s=2c60f69718ea88d4bfcc2aa4c30321641c6638fa

FatTomIV のソリューション: (最適化)
https://i.imgur.com/JOGK8g7.png

先に言わなくてすみません、言い忘れました。

[Hollyleaf]

「2-1-2. Double Trouble」私は https://www.imgpaste.net/image/KBwZ0s より良い解決策だと思います? (機械を使って翻訳したので、不正確な場合は申し訳ありません)

[The heavy is fast]

the code didn't work so i wrote my own, it worked for some tests and in the 18th got an error, the funny part is that i ended up glitching my way out of the level somehow

could be a speedrun strat...