紙テープで足し算をする機械
チューリングマシンとは、無限に長いテープの1マスずつを読み書きして計算する、計算機の最も単純なモデルです。今のコンピュータでできる計算は、この機械でもできると考えられています。
テープ、ヘッド、状態、規則の4つだけで、2進数に1を足すことまでできます。
このレッスンのゴール
メモ
チューリングマシンの規則表をたどって、テープがどう変わるか言える。
重要な言葉
| ことば | いみ | れい |
|---|---|---|
| テープ | 記号を1マスずつ書ける、無限に長い帯 | |
| ヘッド | テープの1マスを読み書きする部分 | |
| 規則 | 読んだ記号から、書く記号と動きを決める1行 | |
| 空白 | 何も書いていないマスの記号 | _ |
| 停止 | 機械が止まる状態に入ること | |
| 向き | ヘッドの動き。右 R、左 L、動かさない S |
学生が入力するセルは、このプレビューでは空白です。
テープとヘッドと規則
機械は、テープ、ヘッド、状態、規則でできています。ヘッドは今いるマスの記号を読み、その状態と記号に合う規則を探します。
規則は3つのことを決めます。書く記号、ヘッドを動かす向き、次の状態です。向きは、右 R、左 L、動かさない S の3つだけです。
2進数に1を足す規則
| 状態 | 読む | 書く | 向き | 次の状態 |
|---|---|---|---|---|
| right | 0 | 0 | R | right |
| right | 1 | 1 | R | right |
| right | _ | _ | L | carry |
| carry | 1 | 0 | L | carry |
| carry | 0 | 1 | S | done |
| carry | _ | 1 | S | done |
学生が入力するセルは、このプレビューでは空白です。
規則を1つ探す
# 規則は [状態, 読む記号, 書く記号, 向き, 次の状態] の並びです。
rules = [
["right", "1", "1", "R", "right"],
["right", "_", "_", "L", "carry"],
]
tape = ["1", "1", "_"]
head = 0
state = "right"
for r in rules:
if r[0] == state and r[1] == tape[head]:
print("見つけた規則:", r)
# head を 2 に変えて、もう一度実行しましょう。
3つの状態の役目
right は、右端の空白まで進む状態です。carry は、繰り上がりを左へ運ぶ状態です。done は停止の状態です。
足し算の手順は、筆算と同じです。まず右端へ行き、そこから左へ戻りながら、1を0にして繰り上げ、0か空白に出会ったら1を書いて止まります。
11 に 1 を足すと
| 手順 | 状態 | テープ（[ ] がヘッド） |
|---|---|---|
| 0 | right | [1]1_ |
| 1 | right | 1[1]_ |
| 2 | right | 11[_] |
| 3 | carry | 1[1]_ |
| 4 | carry | [1]0_ |
| 5 | carry | [_]00_ |
| 6 | done | [1]00_ |
学生が入力するセルは、このプレビューでは空白です。
ラボで機械を動かす
同じ規則を、ラボの端末で動かします。1つ目の Run は tm.py というファイルを作り、画面には何も出しません。
そのあとの Run は、テープに書く2進数を渡します。1行が1ステップで、状態、ヘッドの位置、テープの順に出ます。
機械のファイルを作る
printf 'import sys\nrules = [["right", "0", "0", "R", "right"], ["right", "1", "1", "R", "right"], ["right", "_", "_", "L", "carry"], ["carry", "1", "0", "L", "carry"], ["carry", "0", "1", "S", "done"], ["carry", "_", "1", "S", "done"]]\ntape = list(sys.argv[1]) + ["_"]\nstate = "right"\nhead = 0\nprint(state, head, "".join(tape))\nwhile state != "done":\n for r in rules:\n if r[0] == state and r[1] == tape[head]:\n break\n tape[head] = r[2]\n if r[3] == "R":\n head = head + 1\n if r[3] == "L":\n head = head - 1\n if head < 0:\n tape.insert(0, "_")\n head = 0\n state = r[4]\n print(state, head, "".join(tape))\n' > tm.pyここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
11 に 1 を足す
python3 tm.py 11ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
10 に 1 を足す
python3 tm.py 10ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
1011 に 1 を足す
python3 tm.py 1011ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
よくある間違い
注意
ヘッドは好きなマスへ飛べる、と思いがちです。実際は、1回に動けるのは右か左に1マスだけです。遠くのマスへ行くには、その距離の分だけステップがかかります。メモリの番地を指定する今のコンピュータとは、そこが違います。
規則も文字列で書ける
規則表は、記号の並びです。だから、規則表をテープに書いて読み、その通りに動く機械を、1台作れます。これを万能チューリングマシンと言います。
用途ごとに機械を作り直さず、規則を入れ替える。この考えが、プログラムを入れ替えて使う今のコンピュータの原型です。
さらに挑戦: 1を2つ足す
2進数に1を足す機械を使って、2を足す機械を考えましょう。1を足す機械を2回続けて動かせば、2が足せます。
run_tm の結果をもう一度 run_tm に渡して、"101" に2を足すと "111" になることを確かめましょう。