チューリング機械の動作
一回の遷移で変わる記号・位置・状態を追い、二進数への1加算を学びます。
説明
チューリング機械は、記号を読み書きするテープ、現在位置を指すヘッド、有限個の状態、遷移規則からなる計算モデルです。一回の遷移で現在の状態と記号を調べ、記号を書き、ヘッドを動かし、次の状態へ移ります。
テープ上の二進数へ1を加える機械を作ります。右端まで進んでから、1なら0にして桁上がりを左へ渡し、0なら1にして停止します。1011と111を使い、桁が増える場合まで同じ規則で処理します。
1二進数をテープへ置く
位置0から1011を置き、ヘッドを0にします。未登録の位置は空白記号_として読みます。テープは必要な位置だけ辞書へ保存します。
tape = dict(enumerate('1011'))各位置の記号; head = 0; state = 'scan'開始位置と状態; [(i, tape.get(i, '_')) for i in range(-1, 5)]空白を含むテープ左右に空白があり、ヘッドは最初の1を読みます。scanは右端の空白を探す状態です。位置は負の側にも拡張できるので、桁上がりで左へ伸びても扱えます。
2状態と記号から遷移を選ぶ
規則の値は(次状態, 書く記号, 移動量)です。scanでは0と1を保って右へ進み、空白に来たらcarryへ変わって一つ左へ戻ります。
rules = {('scan', '0'): ('scan', '0', 1), ('scan', '1'): ('scan', '1', 1), ('scan', '_'): ('carry', '_', -1), ('carry', '1'): ('carry', '0', -1), ('carry', '0'): ('halt', '1', 0), ('carry', '_'): ('halt', '1', 0)}全ての遷移規則; print(*rules.items(), sep='\n')規則を一行ずつ表示carryで1を読むと0を書いて左へ進み、0または空白なら1を書いて停止します。このモデルでは移動量0の停止遷移も許しています。別の定義では移動を左右だけに限定することもあります。
3一遷移を実行
現在位置の1を読み、scanと1の規則を取り出します。記号を書いた後でヘッドを動かします。
read = tape.get(head, '_')現在の記号; next_state, write, move = rules[(state, read)]対応する規則; tape[head] = write現在位置へ書く; head += move; state = next_state位置と状態を更新; read, write, move, state, head遷移の結果1を読み1を書き、右へ1移動したのでヘッドは位置1です。読み取り位置と移動後の位置を取り違えないよう、書き込みを移動前に行います。
4残りの走査で右端へ
位置1・2・3の残り3文字を処理します。まだscanなので文字列は変わりません。
for _ in range(3):残り3文字
read = tape.get(head, '_')記号を読む
state, write, move = rules[(state, read)]規則を選ぶ
tape[head] = write記号を書く
head += move移動
print(state, head)更新後の状態と位置位置4に到達しましたが、空白を読む遷移はまだ行っていません。「ヘッドが空白位置に来た」と「その空白の規則を適用した」は別の段階です。
5空白から最下位桁へ戻る
位置4の空白を読むと、carryに切り替えて位置3へ戻ります。
state, write, move = rules[(state, tape.get(head, '_'))]空白に対応する規則; tape[head] = write; head += move空白を保ち左へ; state, head, tape[head]加算を始める位置carry状態で最下位桁の1を読む位置になりました。この1を0へ変えることで、加算の桁上がりを左へ送ります。
6桁上がりを処理して停止
右端の1、次の1を0へ変えて左へ進み、位置1の0を1にしたところで停止します。
while state != 'halt':停止状態まで
read = tape.get(head, '_')現在記号
state, write, move = rules[(state, read)]桁上がりの規則
tape[head] = write記号の書換え
head += moveヘッド移動
print(read, write, state, head, ''.join(tape.get(i, '_') for i in range(4)))読取・書込・状態・位置・全桁1011→1010→1000→1100と変わります。10進数11が12になりました。haltへ入るまでの遷移回数は、走査する長さと末尾に連続する1の個数に依存します。
7全て1なら左へ桁が増える
111の右端からcarryを開始します。走査を終えた状態を初期値として与え、同じ桁上がり規則を適用します。
tape = dict(enumerate('111'))新しい入力; head = 2; state = 'carry'右端の加算開始状態; tape, head, state初期状態を表示全ての1を0へ変えると、位置-1の空白へ到達します。空白にもcarryの規則があるため、そこで新しい1を書いて停止できます。
8左側の空白へ1を書く
停止まで繰り返し、位置-1から2までを表示します。
while state != 'halt':停止まで反復
state, write, move = rules[(state, tape.get(head, '_'))]同じ規則を適用
tape[head] = write空白を含めて書換え
head += move移動
print(state, head, ''.join(tape.get(i, '_') for i in range(-1, 3)))増えた左桁も表示最終的に1000、10進数7に1を加えた8になります。規則と初期状態が決まれば遷移は一意です。ただし、この例が停止することと、任意の機械の停止を一般に判定できることは別の問題です。
まとめ
一遷移は、状態と現在記号から書き込み・移動・次状態を選ぶ操作です。
書き込み位置は移動前のヘッド位置です。状態・位置・テープを一緒に記録すると処理を追えます。
二進数の1加算では右へ走査し、末尾の1を0にしながら左へ桁上がりを渡します。
操作履歴と解説を振り返れます。
Python 3
tape = dict(enumerate('1011')); head = 0; state = 'scan'; [(i, tape.get(i, '_')) for i in range(-1, 5)][(-1, '_'), (0, '1'), (1, '0'), (2, '1'), (3, '1'), (4, '_')]
rules = {('scan', '0'): ('scan', '0', 1), ('scan', '1'): ('scan', '1', 1), ('scan', '_'): ('carry', '_', -1), ('carry', '1'): ('carry', '0', -1), ('carry', '0'): ('halt', '1', 0), ('carry', '_'): ('halt', '1', 0)}; print(*rules.items(), sep='\n')(('scan', '0'), ('scan', '0', 1))
(('scan', '1'), ('scan', '1', 1))
(('scan', '_'), ('carry', '_', -1))
(('carry', '1'), ('carry', '0', -1))
(('carry', '0'), ('halt', '1', 0))
(('carry', '_'), ('halt', '1', 0))read = tape.get(head, '_'); next_state, write, move = rules[(state, read)]; tape[head] = write; head += move; state = next_state; read, write, move, state, head('1', '1', 1, 'scan', 1)for _ in range(3):
read = tape.get(head, '_')
state, write, move = rules[(state, read)]
tape[head] = write
head += move
print(state, head)scan 2 scan 3 scan 4
state, write, move = rules[(state, tape.get(head, '_'))]; tape[head] = write; head += move; state, head, tape[head]('carry', 3, '1')while state != 'halt':
read = tape.get(head, '_')
state, write, move = rules[(state, read)]
tape[head] = write
head += move
print(read, write, state, head, ''.join(tape.get(i, '_') for i in range(4)))1 0 carry 2 1010 1 0 carry 1 1000 0 1 halt 1 1100
tape = dict(enumerate('111')); head = 2; state = 'carry'; tape, head, state({0: '1', 1: '1', 2: '1'}, 2, 'carry')while state != 'halt':
state, write, move = rules[(state, tape.get(head, '_'))]
tape[head] = write
head += move
print(state, head, ''.join(tape.get(i, '_') for i in range(-1, 3)))carry 1 _110 carry 0 _100 carry -1 _000 halt -1 1000
演習完了