前回の構成・様相の再掲

前回示された2記号TMの構成と様相は以下の通りです。本記事では、この2記号TMを記号を先書きTM上で動かす方法を示します。（上図の２つの矢印の部分）

（なお、「先書きTM」は私が勝手につけた名称で、論文中では命名されていないことに注意してください。）

ルール

空白記号： $0$
初期状態： $T_{q_1}$
受理状態： $T_{q_f}$
初期テープと初期ヘッド位置： $…CCC\underline{A}CCC…$ 、←の下線が初期ヘッド位置
ルール：

現在の内部状態	読んだ記号	変化先の内部状態	書く記号	動く方向
$ T_{q_1} $	0	$ T_{q_1, 0} $	0	右
$ T_{q_1} $	1	$ T_{q_1, 1} $	1	右
$ L_{q_1, 0} $	0	$ V_{q_1, 1} $	0	左
$ L_{q_1, 0} $	1	$ V_{q_1, 1} $	0	左
$ L_{q_1, 1} $	0	$ V_{q_1, 1} $	1	左
$ L_{q_1, 1} $	1	$ V_{q_1, 1} $	1	左
$ R_{q_1, 0} $	0	$ U_{q_1, 1} $	0	右
$ R_{q_1, 0} $	1	$ U_{q_1, 1} $	0	右
$ R_{q_1, 1} $	0	$ U_{q_1, 1} $	1	右
$ R_{q_1, 1} $	1	$ U_{q_1, 1} $	1	右
$ T_{q_1, 0} $	0	$ L_{q_f, 0} $	1	左
$ T_{q_1, 0} $	1	$ R_{q_1, 1} $	0	左
$ T_{q_1, 1} $	0	$ L_{q_1, 1} $	0	左
$ U_{q_1, 1} $	0	$ T_{q_1} $	0	右
$ U_{q_1, 1} $	1	$ T_{q_1} $	1	右
$ V_{q_1, 1} $	0	$ T_{q_1} $	0	左
$ V_{q_1, 1} $	1	$ T_{q_1} $	1	左
$ T_{q_f} $	0	$ T_{q_f, 0} $	0	右
$ T_{q_f} $	1	$ T_{q_f, 1} $	1	右
$ L_{q_f, 0} $	0	$ V_{q_f, 1} $	0	左
$ L_{q_f, 0} $	1	$ V_{q_f, 1} $	0	左
$ L_{q_f, 1} $	0	$ V_{q_f, 1} $	1	左
$ L_{q_f, 1} $	1	$ V_{q_f, 1} $	1	左
$ R_{q_f, 0} $	0	$ U_{q_f, 1} $	0	右
$ R_{q_f, 0} $	1	$ U_{q_f, 1} $	0	右
$ R_{q_f, 1} $	0	$ U_{q_f, 1} $	1	右
$ R_{q_f, 1} $	1	$ U_{q_f, 1} $	1	右
$ U_{q_f, 1} $	0	$ T_{q_f} $	0	右
$ U_{q_f, 1} $	1	$ T_{q_f} $	1	右
$ V_{q_f, 1} $	0	$ T_{q_f} $	0	左
$ V_{q_f, 1} $	1	$ T_{q_f} $	1	左

この2記号TMの様相は、以下のように変化していくはずです。
$(…00\underline{0}10…, T_{q1}) \rightarrow (…00\underline{1}00…, T_{q1,0}) \rightarrow ... \rightarrow (…00\underline{1}0010…, T_{qf})$

先書きTMとは?

通常のTMは、①記号を読んで、②記号を書き、③右か左に移動し、④内部状態を変化させるという順番で動作しますが（下図¹）

先書きTMは①記号を書き、②右か左に移動し、③記号を読んで、④内部状態を変化させるという動作を取ります。（下図¹）

このため、この二つの間でルールの形式が少し異なります。（構成法の1節で説明）

構成法

この変換方法は、Cockeさんらによって半分くらい示されました¹。
残りは私が補完しました。

手順を以下に示します。

1. 各ルールを変換する

2記号TMの各ルール１つずつに対して、以下の手順で先書きTMのルールを構成します：

まず、選ばれたルールを以下の表に整理します。

現在の内部状態	読んだ記号	変化先の内部状態	書く記号	動く方向
$q$	$R$	$q'$	$W$	$\text{move}$

そして、次のルールを構成します：

現在の内部状態	書く記号	移動方向	読んだ記号が$0$の時の変化先内部状態	読んだ記号が$1$の時の変化先内部状態
$q^{R}$	$W$	$\text{move}$	${q'}^{0}$	${q'}^{1}$

これで手順は終了です。

このようにして全てのルールを変換すると以下のルール群を得ます。なお、$q'$が受理状態であるなら、その記号をそのまま変化先内部状態に用いることが出来ます。

折り畳み

現在の内部状態	書く記号	移動方向	読んだ記号が$0$の時の変化先内部状態	読んだ記号が$1$の時の変化先内部状態
$ {T_{q_1}}^{0}$	$0$	$R$	${T_{q_1,0}}^{0}$	${T_{q_1,0}}^{1}$
$ {T_{q_1}}^{1}$	$1$	$R$	${T_{q_1,1}}^{0}$	${T_{q_1,1}}^{1}$
$ {T_{q_1,0}}^{0}$	$1$	$L$	${L_{q_f,0}}^{0}$	${L_{q_f,0}}^{1}$
$ {T_{q_1,0}}^{1}$	$0$	$L$	${R_{q_1,1}}^{0}$	${R_{q_1,1}}^{1}$
$ {T_{q_1,1}}^{0}$	$0$	$L$	${L_{q_f,0}}^{0}$	${L_{q_f,0}}^{1}$
$ {L_{q_1,0}}^{0}$	$0$	$L$	${V_{q_1,1}}^{0}$	${V_{q_1,1}}^{1}$
$ {L_{q_1,0}}^{1}$	$0$	$L$	${V_{q_1,1}}^{0}$	${V_{q_1,1}}^{1}$
$ {V_{q_1,1}}^{0}$	$0$	$L$	${T_{q_1}}^{0}$	${T_{q_1}}^{1}$
$ {V_{q_1,1}}^{1}$	$1$	$L$	${T_{q_1}}^{0}$	${T_{q_1}}^{1}$
$ {L_{q_1,1}}^{0}$	$1$	$L$	${V_{q_1,1}}^{0}$	${V_{q_1,1}}^{1}$
$ {L_{q_1,1}}^{1}$	$1$	$L$	${V_{q_1,1}}^{0}$	${V_{q_1,1}}^{1}$
$ {R_{q_1,0}}^{0}$	$0$	$R$	${U_{q_1,1}}^{0}$	${U_{q_1,1}}^{1}$
$ {R_{q_1,0}}^{1}$	$0$	$R$	${U_{q_1,1}}^{0}$	${U_{q_1,1}}^{1}$
$ {U_{q_1,1}}^{0}$	$0$	$R$	${T_{q_1}}^{0}$	${T_{q_1}}^{1}$
$ {U_{q_1,1}}^{1}$	$1$	$R$	${T_{q_1}}^{0}$	${T_{q_1}}^{1}$
$ {R_{q_1,1}}^{0}$	$1$	$R$	${U_{q_1,1}}^{0}$	${U_{q_1,1}}^{1}$
$ {R_{q_1,1}}^{1}$	$1$	$R$	${U_{q_1,1}}^{0}$	${U_{q_1,1}}^{1}$
$ {L_{q_f,0}}^{0}$	$0$	$L$	${V_{q_f,1}}^{0}$	${V_{q_f,1}}^{1}$
$ {L_{q_f,0}}^{1}$	$0$	$L$	${V_{q_f,1}}^{0}$	${V_{q_f,1}}^{1}$
$ {V_{q_f,1}}^{0}$	$0$	$L$	$T_{q_f}$	$T_{q_f}$
$ {V_{q_f,1}}^{1}$	$1$	$L$	$T_{q_f}$	$T_{q_f}$
$ {L_{q_f,1}}^{0}$	$1$	$L$	${V_{q_f,1}}^{0}$	${V_{q_f,1}}^{1}$
$ {L_{q_f,1}}^{1}$	$1$	$L$	${V_{q_f,1}}^{0}$	${V_{q_f,1}}^{1}$
$ {R_{q_f,0}}^{0}$	$0$	$R$	${U_{q_f,1}}^{0}$	${U_{q_f,1}}^{1}$
$ {R_{q_f,0}}^{1}$	$0$	$R$	${U_{q_f,1}}^{0}$	${U_{q_f,1}}^{1}$
$ {U_{q_f,1}}^{0}$	$0$	$R$	$T_{q_f}$	$T_{q_f}$
$ {U_{q_f,1}}^{1}$	$1$	$R$	$T_{q_f}$	$T_{q_f}$
$ {R_{q_f,1}}^{0}$	$1$	$R$	${U_{q_f,1}}^{0}$	${U_{q_f,1}}^{1}$
$ {R_{q_f,1}}^{1}$	$1$	$R$	${U_{q_f,1}}^{0}$	${U_{q_f,1}}^{1}$

2. 入力を変換する

テープは元の2記号TMと同じものを使いますが、先書きTMは初期状態を定義していないその特性上、最初に与える入力に内部状態を含みます。この内部状態は以下で表されます。

{q_0}^{S}

ここで$q_0$は2記号TMの初期状態、$S$は2記号TMの動作開始時のヘッドが指しているテープ位置の記号です。

3. 残りを決めて完成

空白記号：2記号TMの空白記号をそのまま用いる。
受理状態：2記号TMの受理状態をそのまま用いる。
ルール：これまでの手順で示した通り。
初期テープとヘッド位置：2記号TMのものをそのまま用いる。
初期の内部状態：2節で説明したものを入力として使う

今回のTMに適用すると、変換後のTMは以下のようになります。

折り畳み

空白記号；$0$

受理状態：$T_{q_f}$

初期テープと初期ヘッド位置： $…000\underline{0}1000…$

初期の内部状態：${T_{q1}}^0$

ルール：

現在の内部状態	書く記号	移動方向	読んだ記号が$0$の時の変化先内部状態	読んだ記号が$1$の時の変化先内部状態
$ {T_{q_1}}^{0}$	$0$	$R$	${T_{q_1,0}}^{0}$	${T_{q_1,0}}^{1}$
$ {T_{q_1}}^{1}$	$1$	$R$	${T_{q_1,1}}^{0}$	${T_{q_1,1}}^{1}$
$ {T_{q_1,0}}^{0}$	$1$	$L$	${L_{q_f,0}}^{0}$	${L_{q_f,0}}^{1}$
$ {T_{q_1,0}}^{1}$	$0$	$L$	${R_{q_1,1}}^{0}$	${R_{q_1,1}}^{1}$
$ {T_{q_1,1}}^{0}$	$0$	$L$	${L_{q_f,0}}^{0}$	${L_{q_f,0}}^{1}$
$ {L_{q_1,0}}^{0}$	$0$	$L$	${V_{q_1,1}}^{0}$	${V_{q_1,1}}^{1}$
$ {L_{q_1,0}}^{1}$	$0$	$L$	${V_{q_1,1}}^{0}$	${V_{q_1,1}}^{1}$
$ {V_{q_1,1}}^{0}$	$0$	$L$	${T_{q_1}}^{0}$	${T_{q_1}}^{1}$
$ {V_{q_1,1}}^{1}$	$1$	$L$	${T_{q_1}}^{0}$	${T_{q_1}}^{1}$
$ {L_{q_1,1}}^{0}$	$1$	$L$	${V_{q_1,1}}^{0}$	${V_{q_1,1}}^{1}$
$ {L_{q_1,1}}^{1}$	$1$	$L$	${V_{q_1,1}}^{0}$	${V_{q_1,1}}^{1}$
$ {R_{q_1,0}}^{0}$	$0$	$R$	${U_{q_1,1}}^{0}$	${U_{q_1,1}}^{1}$
$ {R_{q_1,0}}^{1}$	$0$	$R$	${U_{q_1,1}}^{0}$	${U_{q_1,1}}^{1}$
$ {U_{q_1,1}}^{0}$	$0$	$R$	${T_{q_1}}^{0}$	${T_{q_1}}^{1}$
$ {U_{q_1,1}}^{1}$	$1$	$R$	${T_{q_1}}^{0}$	${T_{q_1}}^{1}$
$ {R_{q_1,1}}^{0}$	$1$	$R$	${U_{q_1,1}}^{0}$	${U_{q_1,1}}^{1}$
$ {R_{q_1,1}}^{1}$	$1$	$R$	${U_{q_1,1}}^{0}$	${U_{q_1,1}}^{1}$
$ {L_{q_f,0}}^{0}$	$0$	$L$	${V_{q_f,1}}^{0}$	${V_{q_f,1}}^{1}$
$ {L_{q_f,0}}^{1}$	$0$	$L$	${V_{q_f,1}}^{0}$	${V_{q_f,1}}^{1}$
$ {V_{q_f,1}}^{0}$	$0$	$L$	$T_{q_f}$	$T_{q_f}$
$ {V_{q_f,1}}^{1}$	$1$	$L$	$T_{q_f}$	$T_{q_f}$
$ {L_{q_f,1}}^{0}$	$1$	$L$	${V_{q_f,1}}^{0}$	${V_{q_f,1}}^{1}$
$ {L_{q_f,1}}^{1}$	$1$	$L$	${V_{q_f,1}}^{0}$	${V_{q_f,1}}^{1}$
$ {R_{q_f,0}}^{0}$	$0$	$R$	${U_{q_f,1}}^{0}$	${U_{q_f,1}}^{1}$
$ {R_{q_f,0}}^{1}$	$0$	$R$	${U_{q_f,1}}^{0}$	${U_{q_f,1}}^{1}$
$ {U_{q_f,1}}^{0}$	$0$	$R$	$T_{q_f}$	$T_{q_f}$
$ {U_{q_f,1}}^{1}$	$1$	$R$	$T_{q_f}$	$T_{q_f}$
$ {R_{q_f,1}}^{0}$	$1$	$R$	${U_{q_f,1}}^{0}$	${U_{q_f,1}}^{1}$
$ {R_{q_f,1}}^{1}$	$1$	$R$	${U_{q_f,1}}^{0}$	${U_{q_f,1}}^{1}$

動作の概説

守「この変換後のTMの動作は、変換前TMの動作をずらしただけなんですよね。」

じ「上が通常のTM、下が先書きTMか。確かにかなり似ているが、"State $Q_i$" と "Read Tape" の順番が違うというのはまずいんじゃないか？」

守「先書きTMでは、$ {T_{q_1}}^{0}$ の様に、内部状態の右肩に$0$か$1$がついているものを使いますが、この$0$や$1$がその前に読んだ記号を示しているのです。」

じ「内部状態に読んだ記号を覚えさせているという事か。なるほどそれなら順番が逆でもいいのだな。...ん？最初の赤い四角は？」

守「一番最初の内部状態にも読んだ記号を覚えさせなければいけないので、入力を変換するときにテープを読んでしまって、その情報を持った内部状態からスタートさせているのです。構成法の以下の部分を思い出してみてください」

テープは元の2記号TMと同じものを使いますが、先書きTMは初期状態を定義していないその特性上、最初に与える入力に内部状態を含みます。この内部状態は以下で表されます。
{q_0}^{S}
ここで$q_0$は2記号TMの初期状態、$S$は2記号TMの動作開始時のヘッドが指しているテープ位置の記号です。

解釈

守「先ほどのTMを止まるまで（受理状態になるまで）動かしたときの様相は以下のようになります。」

…00\underline{1}0010…, T_{q_f}

じ「2記号TMの終了時の様相と全く同じになるんだな。」

守「ずらしただけですからね。」

ライセンス

この記事で使われている一部の画像は、Magic:the Gathring のカードイラストから切り抜いたものです。Wizards of the Coast社の認可/許諾は得ていません。

COCKE, John; MINSKY, Marvin. Universality of tag systems with P= 2. Journal of the ACM (JACM), 1964, 11.1: 15-20. ↩ ↩² ↩³

2記号TM ⇔ 先書きTM【3/6】