チューリング完全性

本稿では，sasanqua_neufのチューリング完全性を証明します．具体的には，チューリングマシンのエミュレータを構成することでチューリング完全性を示します．

概要

sasanqua_neufのテープTをチューリングマシンのテープと「概ね」同一視し，チューリングマシンの状態をCの値によって「概ね」表現します．C言語風にエミュレータの概要を記すと，全体の構造としては

int Cq=1;
while(Cq != n+1){
  switch(Cq){
  case 1:  //qの添え字が1
    switch(T[H]){  //T[H]にσが格納されている
    case 1: //σの添え字が1
      T[H] = [δ_2(q_1,σ_1)];  //T[H]をテープと同一視
      H += [δ_3(q_1,σ_1)];    //ただしLeft=-1,Right=+1と見て
      while(T[H] == 0){getchar();}  //テープの中身が0のとき，未入力とする
      Cq = [δ_1(q_1,σ_1)];
    break;
    case 2: //σの添え字が2
      T[H] = [δ_2(q_1,σ_2)];
      ...	//σ_3,σ_4,...,σ_m
    }
  break;
  case 2:  //qの添え字が2
    ...	//q_3,q_4,...,q_n
  }
}

に近いものになります（各変数は適当に初期化・定義されているとし，またq,σ,δ等の定義は下を参照してください）．

ただし，証明で与えるsasanqua_neufのコードでは，switch(およびwhile)を用いる代わりに直接目的とするコードの先頭にジャンプする方法を用いています．また，sasanqua_neufではT[H]の値がしばしばジャンプに必要となるため，テープの値をルーチン限度数に「代わりに」保存することもあります．（そのため，Tとチューリングマシンのテープを「概ね」同一視する，という言い方になっています．）

なお，上のコードはswitchに関する冗長性を除けば

int Cq=1,i;
while(Cq != n+1){
  i=T[H];
  T[H] = [δ_2(q_Cq,σ_i)];
  H += [δ_3(q_Cq,σ_i)];
  while(T[H] == 0){getchar();}
  Cq = [δ_1(q_Cq,σ_i)];
}

と本質的に等しく，これはチューリングマシンのエミュレータを与えます（getcharがテープから新しい文字（の添え字）を受け取ると見て）．

証明

チューリングマシン(Q,Γ,Σ,δ)が与えられたとする．
Q={q_1,...,q_n,q_{n+1}}をその状態で，特にq_1を初期状態，q_{n+1}を受理状態とする．
Γ={σ_1,...,σ_m}を記号とし，σ_1を空白記号，Σ=Γ＼{σ_1}を入力記号とする．
δ:Q×Γ→Q×Γ×{Left,Right}を遷移関数とし，δ(q,σ)=(δ_1(q,σ),δ_2(q,σ),δ_3(q,σ))とおく．
また，[q_i]=[σ_i]=i，[Left]=-1,[Right]=+1とおく．

ルーチンR_a=1278345691,R_b=4561237899とする．R_aとR_bが対戦するとき，先手後手に関わらずR_bが必ず勝つ．また，R_b同士が対戦した場合には引き分けになる．

補題：

sasanqua_neufを実行中とする．対局終了後に L_1=L_2=0 になったと仮定し，さらにT[H]は 0＜i＜m+1（mは記号数）なる自然数について T[H]=i をみたし，C の値は下記☆の位置に対応していたとする．また，もし T[H±1]=0 なら T[H±2]=0 （複号はそれぞれ対応）と仮定する．
このとき，次のコード断片は，Cの値がコード断片の領域に対応する値を超えてから初めてのルーチンセットを行うまでに，「結果的に」下記１，２，３の変化のみを引き起こす．

コード断片：

   R_b 1 1
   R_a 1 1
   R_b 2 1 ([δ_3]=1)  or  R_a 1 1 ([δ_3]=-1)
   R_a 1 1 ([δ_3]=1)  or  R_b 4 1 ([δ_3]=-1)
   R_b 1 4 
   R_b 1 4 
   * (*は任意のコード)
   * 
   * 
   * 
   R_a 1 0
   R_b 1 0
   R_b 1 Y1 (ただしY1はこの行から★の行までの行の量-5)
   R_b 1 Y1   (□にジャンプする)
   R_a 1 1
   R_b 1 1
   R_b 1 Y2+1 (ただしY2=Y1-4)
   R_b 1 Y2   (□にジャンプする)
   ...  |
   ...  | 3,4, ... ,m-1
   ...  |
   ...  |
   R_a 1 m-1
   R_b 1 m-1
   R_b 1 Ym+m-1 (Ym=4 , Ym+m-1=3+m)
   R_b 1 Ym
☆ R_a 1 i-[δ_2] (i＞[δ_2])  or  R_b 1 [δ_2]-i (i≦[δ_2])
　 R_b 1 i-[δ_2] (i＞[δ_2])  or  R_a 1 [δ_2]-i (i≦[δ_2])
   R_b 2 1 ([δ_3]=1)  or  R_a 1 1 ([δ_3]=-1)
   R_a 1 1 ([δ_3]=1)  or  R_b 4 1 ([δ_3]=-1)
□ R_a 1 0 
   R_b 1 12 
   R_b 1 12 
★ R_b 1 1 ([δ_3]=1)  or  R_a 1 1 ([δ_3]=-1)
   R_a 1 1 ([δ_3]=1)  or  R_b 1 1 ([δ_3]=-1)
   R_a 1 1 
   R_b 7 1 
   R_b 3 1 
　 R_a 1 1 
   R_b 2 1 ([δ_3]=1)  or  R_a 1 1 ([δ_3]=-1)
   R_a 1 1 ([δ_3]=1)  or  R_b 4 1 ([δ_3]=-1)
   R_a 1 1
   R_b 1 1
   R_b 1 X (ただしXはこのコード断片の行の量)
   R_b 1 X 

ただし，q∈Q はある状態であり，δ_2=δ_2(q,σ_i) , δ_3=δ_3(q,σ_i) はその引数を省略した．また，見やすくするためにルーチン，終了処理，限度数の間にはそれぞれ空白を入れているが，この空白は無視されるものとする．また，or と書いてある部分は，()内のいずれを満たすかによって断片を変えるものとする（()のいずれを満足するかは与えられた条件から一意的に定まる）．

補題の証明：

上の仮定のもとで，コードの実行を追うことにする．i＞[δ_2] のとき，☆以下２行のルーチンの使用を終えるとき T[H]→[δ_2] なることは定義から明らか．i≦[δ_2] の場合も同様で，いずれも同時に L_1=L_2=0 になる．また，その次の２行で H→H+[δ_3] なることも明らかで，やはり同時に L_1=L_2=0 になり□の行は無視される．
次の２行を読み込むと，C が★に対応する状態から C→C+8×T[H] となるので，T[H]＞0 のときは主張は正しい．
以下，T[H]=0 と仮定する．このとき，同時に L_1=L_2=0 となって★以下２行を読み込むことになるが，これは実行されると T[H]→T[H]+[δ_3]=[δ_3] となる．その次の２行でこの値を出力する．次の２行は，一度だけ入力を要求する．次に H を更に H→H+[δ_3] とするが，このとき仮定より新しい H について T[H]=0 である．よって，この次の操作で必ず T[H]=-1 になる．その後最後の２行を読み込むと，T[H]=-1 の条件下でX回対局を繰り返すことになり，Cはこのコード断片の先頭に対応する値になる．
先頭部分のはじめの２行を読み込んで対局が終了すると T[H]=0,L_1=L_2=0 になる．（すなわち，ここで移動に用いたT[H]を0に「修復」している）．
次の２行を読み込んで対局が終了すると H→H-[δ_3] となる．その次の２行を読み込むと，T[H]=(上で要求した入力の値) の4倍だけCを増やして L_1=L_2=0 となる．このT[H]の値をkとおくと，コード断片
R_a 1 k-1
R_b 1 k-1
R_b 1 Yk+k-1
R_b 1 Yk
は T[H]→1 とし，更に□の位置までCを増やしたところで L_1=k-1,L_2=0 となり，次のルーチンセットで L_2 には k-1 がセットされる．ここで対局を繰り返すと L_1=L_2=0 となって，T[H]=k となる．次の２行を読み込んでからの動作は，上で述べた T[H]>0 の場合と同様で，上で T の値を「修復」していることから所期の結論を得る．q.e.d.

※補題の部分は，冒頭のC言語風の記述でいえば，二つのswitchの中身の部分のうち，Cq = [δ_1(q_Cq,σ_i)];以外の部分に対応しています．

定理：

任意のチューリングマシンに対し，（テープに書き込まれたσ_iの代わりにiを入力として受け取ることで）チューリングマシンをエミュレートするようなsasanqua_neufのコードが存在する．

定理の証明：

[q]=j，すなわちq=q_jとする．上の（qおよびi=T[H]に依存する）コード断片の末尾に，次の断片（および下記の補足）を継ぎ足したコードをCODE(j,i)とする．

   R_a 1 0 ([δ_3(q_j,σ_i)]＞q_j)  or  R_a 1 2 ([δ_3(q_j,σ_i)]≦q_j)
   R_b 1 0 ([δ_3(q_j,σ_i)]＞q_j)  or  R_b 1 2 ([δ_3(q_j,σ_i)]≦q_j)
   R_b 1 Z1   ([δ_3(q_j,σ_i)]＞q_j)  or  R_b 1 Z1+2 ([δ_3(q_j,σ_i)]≦q_j)
   R_b 1 Z1   ([δ_3(q_j,σ_i)]＞q_j)  or  R_b 1 Z1   ([δ_3(q_j,σ_i)]≦q_j)
   *    |
   *    |
   ...  | 8行
   *    |
   R_a 1 1 ([δ_3(q_j,σ_i)]＞q_j)  or  R_a 1 3 ([δ_3(q_j,σ_i)]≦q_j)
   R_b 1 1 ([δ_3(q_j,σ_i)]＞q_j)  or  R_b 1 3 ([δ_3(q_j,σ_i)]≦q_j)
   R_b 1 Z2+1 ([δ_3(q_j,σ_i)]＞q_j)  or  R_b 1 Z2+3 ([δ_3(q_j,σ_i)]≦q_j)
   R_b 1 Z2   ([δ_3(q_j,σ_i)]＞q_j)  or  R_b 1 Z2   ([δ_3(q_j,σ_i)]≦q_j)
   *    |
   *    |
   ...  | 8行
   *    |
   ...   |
   ...   |
   ...   |
   ...   |
   ...   |
   ...   |
   ...   |
   ...   |  3,4,...,m-1
   ...   |
   ...   |
   ...   |
   ...   |
   R_a 1 m-1 ([δ_3(q_j,σ_i)]＞q_j)  or  R_a 1 m+1 ([δ_3(q_j,σ_i)]≦q_j)
   R_b 1 m-1 ([δ_3(q_j,σ_i)]＞q_j)  or  R_b 1 m+1 ([δ_3(q_j,σ_i)]≦q_j)
   R_b 1 Zm+m-1 ([δ_3(q_j,σ_i)]＞q_j)  or  R_b 1 Zm+m+1 ([δ_3(q_j,σ_i)]≦q_j)
   R_b 1 Zm     ([δ_3(q_j,σ_i)]＞q_j)  or  R_b 1 Zm     ([δ_3(q_j,σ_i)]≦q_j)
   *    |
   *    |
   ...  | 8行
   *    |

このコードを補題のコードの下に結合したものが，CODE(j,i)である．ただし，各断片のZkは一般にj,iに依存して決まる量で，δ_3(q_j,σ_i) に対応する適切なCの値になるように定義されるのだが，後で詳しく述べる．
CODE(j,i) の☆から最後の行までの行数を K(=12m+19) , 全ての行の数を M(=16m+29) とする（CODEの行数はj,iによらず一定である）．

ここで，各 j=1,2,...,n について次のコード断片CODE'(j)を作る．

   R_a 1 0
■ R_b 1 M
   R_b 1 M
   *    |
   *    |  K行
   ...  |
   *    |
   CODE(j,1)
   CODE(j,2)
   ...
   CODE(j,m)

CODE'(j) は，Cが■に対応しているときに L_1=L_2=0 , 0＜T[H]=i＜m+1 になったと仮定すると，その次に C を CODE(j,i) の☆に「T[H]およびHを不変のまま」移動させて，L_1=L_2=0 にすることに注意する．CODE'(j) の長さは m(16m+29)+(12m+19)+3 = 16m^2+41m+22 である．

さて，今度は CODE'(j) を用いて

   R_b 3 1
   R_a 1 1
   CODE'(1)
   CODE'(2)
   ...
   CODE'(n)
   R_a 1 0

なるコードCODE"を作る．このコードこそが，（各j,iに対してCODE(j,i)中のZ1,...,Zmを適当に定めることで）実はチューリングマシンのエミュレータになっている，ということを示そう．

CODE"を実行したとき，初めにテープのヘッド位置にある文字（に対応する添え字）を入力し，以下CODE"から-1を出力後の入力要求には「未入力のテープの情報のうち，今まで入力したものの最も左の場所のひとつ左の場所に書いてある文字（の添え字）」を，1を出力後の入力要求には「未入力のテープの情報のうち，今まで入力したものの最も右の場所のひとつ右の場所に書いてある文字（の添え字）」を，それぞれ入力することにする．

ところで，CODE'(j)の■について注意した事実に注意すると，
１．CODE'(j)の先頭で L_1=L_2=0 になれば，先頭に来たときの T,Hの値がそのまま保存されて CODE(j,T[H]) の☆に移動する．特に，CODE"のはじめの２行の実行後は，CODE(1,i) (iは初めに入力された値)の☆に移動する．
２．CODE'(j) の先頭で，先手のルーチンがR_b，先手の終了処理が E_1=1 ，両者の限度数が L_1=L＞0,L_2=0 になったとき，対局を続けると T[H]→T[H]+L になったところで L_1=L_2=0 になる．このとき C は■に対応する位置にあるから，結果として（元のT[H]に対して）CODE(j,T[H]+L) の☆の位置に移動する．
が言える．この１，２より，もしCODE(j,i) の各Zkに対して「 CODE'([δ_3(q_j,σ_i)]) の先頭に移動したところでL_2=0になる」ような値が与えられていれば，CODE"が（上のテープの入力ルールのもとで）チューリングマシンと等しい動作をすることが帰納的に示される．

そのようなZkは実際に計算で求まる（Zkの値によらずコードの行数が変化することはないから，計算できる）．従って，CODE"は上の入力ルールのもとでチューリングマシンをエミュレートするコードである．q.e.d.

系：

sasanqua_neufはチューリング完全である．

※チューリングマシンのテープの初期値に（必ずしも規則的でない）無限列を含めない場合は，状態数を適当に増やすことで「テープの初期値が全て空白のチューリングマシン」によって任意の結果をエミュレートできるので，入出力が不要になりもっとコードが短くなります．