Wolfram's (2, 3)-Turing machineの「普遍性の証明」を読む

ここで，(2, 3)-Turing machineとはstateが2つ，テープalphabetsが3つのTuring machineのこと。alphabetsを{0, 1, 2}とおき，statesを{A, B}とおく。Wolframが次の遷移規則の(2, 3)-Turing machineが普遍 (universal) か否かに懸賞金25,000 USDをかけた。

A B
0 1, →, B 2, ←, A
1 2, ←, A 2, →, B
2 1, ←, A 0, →, A

（たとえば，左上の規則(A, 0; 1, →, B)は「state Aで0を読んだとき，1を書き，右に移動し，state Bに遷移する」と読む。）

2007年5月14日，Alex Smithの肯定的な答え (https://www.wolframscience.com/prizes/tm23/TM23Proof.pdf) にWolfram Researchが懸賞金を出したことが発表されたが，メーリングリストFOM -- Foundations of Mathematicsの議論によれば通常の意味でのuniversal Turing machineであることの証明にはなっていないという話もあったりして，どういうことか自分で読んで確かめてみることにした。

最初にこの日記の結論を書いてしまうと，まあまあ面白かったが，かなり駄目な感じ。当時学部学生だったAlex Smithは良いけど，何のフォローもしないままこれを大々的に発表したWolfram Researchははっきり言って【あとで書く】

Turing machineの無駄を取り除く

Alex Smithの記法に従って，元の(2, 3)-Turing machineをsystem 0とよぶ。system 0と本質的に動作が同じで解析が簡単なsystem 3をまず構成している。Turing machineは現在のヘッドの位置のセルしか読み書きできないが，1つ右のセルも読み書きできるようなsystemを考えると今回は都合が良くなる。この部分の議論は3段階からなるので，勝手にa., b., c.とよぶことにする。

だいたい，図の青丸で囲んだ部分が「無駄」なことと，青線の前後で色が入れ替わるのが「見にくい」ことを対処している。

考察a. system 0でsystem 1を模倣*1：(B, 2; 0, →, A)の次の次に(A, 0; 1, →, B)で上書きする場合について3 stepsを1 stepにまとめる。

考察b. system 1でsystem 2を模倣：読み出し時にalphabetsの1, 2を入れ替えるhookがかかるstate Bを考え，それをstate Cとおく。system 1は右セルに依存して右セルを書き換えていたが，system 2は右セルに依存するものの右セルを書き換えなくなった。後の議論を考える上では，Cはcarry（繰り上がり）のCだと覚えると良さそう（ただし，原論文にはそう書かれてはいない）。

考察c. system 2でsystem 3を模倣：テープのうちヘッドの左側（state Aのときはinclusive，state B or Cのときはexclusive）の1, 2を入れ替える。これで，state Aの挙動が「0が現れるまで左に行って2を書いて右に1歩戻ってstate Bに遷移」になる。

ここで定義されたsystem 3は

A B C
0 2, →, B 2, ←, A 2, ←, A
1（右が1 or 2） 1, ←, A 1, →, B 2, →, C
1（右が0） 1, ←, A 1, →, B 0, →, A
2（右が1 or 2） 2, ←, A 2, →, C 1, →, B
2（右が0） 2, ←, A 0, →, A 1, →, B

となっていて，同じ文字での上書き，同じ状態への遷移を省略すると，

A B C
0 2, →, B 2, ←, A 2, ←, A
1（右が1 or 2） ← → 2, →
1（右が0） ← → 0, →, A
2（右が1 or 2） ← →, C 1, →, B
2（右が0） ← 0, →, A 1, →, B

となる。Alphabets 1, 2のみが現れる部分の見通しが良くなっているのがポイント。

補足

原論文の考察a.のところを少し変えて，(B, 2; 0, →, A)での0の書き込みを遅延させると考え，

A B C
0 2, →, B 2, ←, A ←, 0, →, A
1 ← → 2, →
2 ← →, C 1, →, B

とする方が分かりやすそう。さらに，alphabetsを{#, 0, 1}にして，

A B C
# 1, →, B 1, ←, A ←, #, →, A
0 ← → 1, →
1 ← →, C 0, →, B

をsystem 3'とおく。以下ではこれをsystem 3の代わりに用いて（system 4までの）議論をする。

set, scan, parity

さて，system 3'でテープの左に戻るには#を他のalphabetsに書き換えなければならないことに注目する。テープの左右（無限にのびているところ）以外に#が「ほとんど」ない場合に限定して考察することになる。

Lemma 1では0, 1のみが並んでいる箇所に着目する。原論文ではalphabets 0, 1からなるL=2w個の並び（wは0以上の整数）を単にsetとよんだりしているが，ここでは，順不同な「集合」と区別するためにセットと表記する。ちなみに，Lemma 1.1以外では個数が2べきという制約が不要。

セットの左端のセルでstate B or Cになっていたときを考える。L steps後にセットの右に隣接するセルに到達し，この間state Aにはならない。このL stepsをスキャンとよぶ。（ただし原論文では，スキャンの開始時点のことをscanとよんでいる。）

スキャン前後のstatesについてB, Cをそれぞれ0, 1とみなすことで，stateとセット（Lセルからなる）のスキャンでの変化は線形写像

f: F2 × F2L → F2 × F2L（ここで，F2 = Z/2Z）

f(s, (xi)i=0…L-1) = (s + Σj=0…L-1 xi, (s + Σj=0…i xi)i=0…L-1)

となる。*2

Haskellっぽく書くと，

f 0 xs = (last ys, ys) where ys = scanl1 (+) xs

とくに，セットのparityを1の個数の偶奇（すなわち Σj=0…L-1 xi）として定めると，次が分かる（Lemma 2.2の言い換え）：

  • parityが0 (mod 2)だったとき，スキャン前後のstateは等しく，
  • parityが1 (mod 2)だったとき，スキャン前後のstateはB, Cのうち逆のものとなる。

つまり，スキャンによってセットのparityを読み出すことができる。

自然数の集合のエンコード

スキャンによってセットは変化しているので，次に同じセットをスキャンするときには異なる（かもしれない）parityを読み出せる。セットのあるスキャンの終了時と次のスキャンの開始時のセットが等しいことが分かる。（なぜなら，考慮すべき唯一の場合は，スキャン終了直後にセットの右端のセルで1が#に書き換えられる場合だが，このセルにヘッドが通りがかるときに1に戻される。）

B, Cどちらのstateでスキャンするかによって次に読むときのparityに影響がある……と思いきや，L=2wのときは， 2w回以下のスキャンの結果は変わらない。(Corollary 0)

例えば，L=8=23のとき，0回目のスキャン前のstateの差が初めて影響するのは8回目となる（線形性より差のみを考えれば十分）。

  • f(1, (0, 0, 0, 0, 0, 0, 0, 0)) = (1, (1, 1, 1, 1, 1, 1, 1, 1))
  • f(0, (1, 1, 1, 1, 1, 1, 1, 1)) = (0, (1, 0, 1, 0, 1, 0, 1, 0))
  • f(0, (1, 0, 1, 0, 1, 0, 1, 0)) = (0, (1, 1, 0, 0, 1, 1, 0, 0))
  • f(0, (1, 1, 0, 0, 1, 1, 0, 0)) = (0, (1, 0, 0, 0, 1, 0, 0, 0))
  • f(0, (1, 0, 0, 0, 1, 0, 0, 0)) = (0, (1, 1, 1, 1, 0, 0, 0, 0))
  • f(0, (1, 1, 1, 1, 0, 0, 0, 0)) = (0, (1, 0, 1, 0, 0, 0, 0, 0))
  • f(0, (1, 0, 1, 0, 0, 0, 0, 0)) = (0, (1, 1, 0, 0, 0, 0, 0, 0))
  • f(0, (1, 1, 0, 0, 0, 0, 0, 0)) = (0, (1, 0, 0, 0, 0, 0, 0, 0))
  • f(0, (1, 0, 0, 0, 0, 0, 0, 0)) = (1, (1, 1, 1, 1, 1, 1, 1, 1))

また，この例で現れる2w個のセットはF22wの基底をなすので，

  • セットに書かれたalphabetsの列と
  • 0回目から2w-1回目のスキャンで読まれるparityの列

の間に全単射g: F22w → F22wがある。*3よって，0以上2w未満の整数の集合を長さ2wのセットにエンコードすることができる。(Method 2)

例えば，w=3で，

  • {0} ↦ 10000000
  • {1} ↦ 11000000
  • {2} ↦ 10100000
  • {3} ↦ 11110000
  • {4} ↦ 10001000
  • …
  • {7} ↦11111111
  • {1, 4, 7} ↦ 11000000 xor 10001000 xor 11111111 = 11010111

などのようになる。

スキャンを遷移に

ここからは，長さが2べきのセットのみを考える。また，以後の議論はどのセットもスキャンが2w回以下しか行われないように注意しなければならない。

さらに，

  • ヘッドの左にあるセットの右端の1セル，または
  • ヘッドの右にあるセットの左端の1セル

に限り#が書かれていることを許すことにする。

  • 前者については，そのセットから読み出されるparitiesは#の代わりに1が書かれている場合と等しくなる。
  • 後者については，初めてそのセット（の左端の#が書かれたセル）に到達したときに，stateがBかCかで読み出されるparitiesが変わる。
    • State Bの場合，1, ←, Aが実行されるので，スキャンされなかっとみなし，#の代わりに1が書かれている場合と等しくなる。
    • State Cの場合，←, #, →, (A), 1, →, Bとなるので，（#の代わりに1が書かれていた場合に0, →, Bとなることと比較して，）今回読み出されるparityは等しく次にスキャンするときのセットは左端のセルが1か0かのみ異なる。よって，1回目（この日記では回数は0回目から数えていることに注意）のparityのみが変わることになる。

（p. 12から始まるWhy the initial condition worksの2, 4, 5でこのような議論がされている……と思う。）

この考察をまとめると，system 4が得られる：テープの各セルには，0以上2w-2未満の整数の集合または新しいalphabet *が書かれている。ただし*が書かれているセルが隣接してはならない。この*は#の書かれている位置を表す。遷移規則は

A B C
集合S (0 ∈ S) ← (S - 1), → (S - 1), →
集合S (0 ∉ S) ← (S - 1), →, C (S - 1), →, B
* セルを削除しながら← セルを削除しながら←, A →, (S xor {1})

where S - 1 = { n - 1 | n ∈ S, n ≥ 1 }, S xor {1} = (S ∪ {1}) \ (S ∩ {1})

system 3'での（あらかじめ決められたstep数の実行について，十分大きいwを適切に選んだ）system 4の模倣は次の例のようになる。この例ではw=3とする。

  • system 4の状態として，テープが… {3} * {1, 4} {1, 5} * {2} …であって，ヘッドが{1, 4}のところを指しているとする。
  • 2w-2=6, 2w-2=7で調整して，{3, 6, 7}, {1, 4, 7}, {1, 5, 7}, {2, 6, 7}をエンコードすると順に11100001, 11010111, 11110011, 10110001となる（それぞれのセットの両端が1となるようにした）。
  • system 3'のテープは，… 1110000# 11010111 11110011 #0110011 …（説明のために8セルからなるセットごとに空白で区切った）。ヘッドは8セル目（{1, 4, 7}に対応するセットの左端のセル）を指している。

（帰着できていることを確かめるとき，system 4の遷移(C, *; →, (S xor {1}))では*の扱いが変わることに混乱してた。）

原論文では，この時点で（両側ではなく）右側のみ無限にのびているテープを考え，テープの左端については特殊な扱いをするが，省略。

これをさらに整理

特別なテープの状態に限定した場合のsystem 4を考え，system 5を得る。System 4によるsystem 5の模倣には十分大きいパラメータfをとる必要があるらしい。

System 5は1以上の整数の集合の非空有限列の書き換え規則。最初の集合と残りの集合は扱いが異なるのでそれを反映した記法にしておこう。

  • (S; R0, R1, …) → (S - 1; R0 + 1, R1 + 1, …) if 1 ∉ S
  • (S; R0, R1, …) → (((S - 1) \ {0}) xor (R0 + 1); R1 + 1, R2 + 1, …) if 1 ∈ S

この帰着ではsystem 4のヘッドがセミコロン(;)で表したあたりを往復する場合に限定されている。（*をはさまず）連続しているセットは続いてスキャンされるが，それらのスキャンをまとめて考えるとparitiesのxorとなることが主要な考察っぽい。この考察以外の原論文での議論をあまり追っていない。

system 5をcyclic tag systemに帰着しようとしている

あらかじめcyclic tag systemを次のように変換しておく：(110; 11, 0, 01, ε) ↦ (111100; 1111, ε, 00, ε, 0011, ε, ε, ε)

具体例でまず説明すると，working string 111100を{1, 3, 4, 6, 7, 9, 10, 12, 13, 14, 15, 16}に変換。3-1=2, 6-4=2, 9-7=2, 12-10=2, 14-13=1, 16-15=1を間をあけて並べた。また最初のrule 1111は{21, 24, 27, 30}, {19, 22, 25, 28}に変換される。（一般には，ruleで同じalphabet 2個ずつ並ぶように変換してあったことを使う。）

Cyclic tag systemの(111100; 1111, ε, 00, ε, 0011, ε, ε, ε) → (111001111; ε, 00, ε, 0011, ε, ε, ε, 1111)に対応して，system 5では
({1, 3, 4, 6, 7, 9, 10, 12, 13, 14, 15, 16}; {21, 24, 27, 30}, {19, 22, 25, 28}, {}, （中略）, {})
→ ({2, 3, 5, 6, 8, 9, 11, 12, 13, 14, 15, 22, 25, 28, 31}; {20, 23, 26, 29}, {}, （中略）, {})
→ ({1, 2, 4, 5, 7, 8, 10, 11, 12, 13, 14, 21, 24, 27, 30}; {21, 24, 27, 30}, {}, （中略）, {})
→ ({1, 3, 4, 6, 7, 9, 10, 11, 12, 13, 20, 22, 23, 25, 26, 28, 29, 30}; {}, （中略）, {})
となる。3-1=2だったので，8つの元が最初の（working setともいうべき）集合に追加されたが，この差が1だと打ち消しあってしまうので「追加しない」ことを表せる。

問題は使用したruleを後ろに戻していないことで，原論文では「ruleをcyclicにする部分は自分で十分な回数あらかじめ複製しておいてね」という議論をすることになる。この日記では，ruleがwrapping backしない「嘘cyclic tag system」のことをfinite tag systemとよぶことにする。一応，finite tag systemを正確に定義をしておくと，

  • (S; R0, …, Rr-1)の書き換え（S, Riは0, 1からなる文字列）
    • (0S; R0, …, Rr-1) → (S; R1, …, Rr-1)
    • (1S; R0, …, Rr-1) → (SR0; R1, …, Rr-1)
    • (S; ) のとき完了
  • 完了までにSが空文字列εになったら停止
    • 後の都合のため，停止した場合は(ε; R0, …, Rr-1) → (ε; )の後に完了することにしておく

まあともかく，与えられたfinite tag systemについて，十分大きいパラメータ (w, f) のsystem 5で模倣できることが示されている。*4

ただし，finite tag systemの停止は，空集合のエンコード*5となっていることで表されるため，停止判定はデコードされていない。つまり，特定のセル1つに書かれたalphabetを確かめればよいようになっていないどころか，模倣に必要なパラメータに応じた個数のセルのalphabetsを（何か別の機械で）デコードすることで停止かどうか分かる。

From arbitrary to infinite (p. 21)

とはいえ，Alex Smithも任意有限と無限の違いが問題となることはちゃんと認識していて「ある意味で無限にできる」ことを主張してくる。実は，system 0でfinite tag systemを模倣するとき以下のようになっているのでcyclic tag systemの模倣のstep数を0, 1, 2, …と増やしたものを左から並べればよい。

  • テープのうち有限長のみを初期化し，そのうち最も左のセル（alphabet 0が書かれている）からstate Aで始める。
  • System 0による模倣の間はヘッドは初期化範囲を出ない。
  • 模倣は（停止するかにかかわらず）完了し，そのとき初期化範囲のすぐ右セルに（初めて）到達しstate Aになる。

……ちょっと待て，そんな複雑な初期化（しかも無限長）をして良いの？

初期化がnon-universalか

勝手な初期化を許せば

A
0 →
1 停止

さえもuniversalと言えてしまう。実際，nセル目の初期化を「模倣されるTuring machineがn stepsで停止するときに1，そうでなければ0」とすれば良い。

Alex Smithもこういうまずさは考慮しようとしていて，「初期化をnon-universalに行ってから計算してuniversalになるから，systemがuniversal」という主張になっているようだ。

しかし，この「n stepsで停止するか」で初期化する例でも，nを固定するごとには，「Turing machineのn step後に停止しているか」は決定可能なためuniversalではない。原論文の議論もcyclic tag systemの模倣の制限step数ごとの議論なので，これを許してしまうようにみえる。

もちろん，system 0に与える初期テープへのcyclic tag systemからの変換は（すべてのnについて並べて無限文字列を作っているとはいえ），すべてのnについて並べてもあまりuniversalっぽくはないが，有限文字列から無限文字列へのこの変換がどういう定義でuniversalと考えられるかの定義を与えるべきだったように思う。

最初に書いたメーリングリストFOMでの議論を見てみると，universal Turing machineの定義で，たとえば，Turing machineを変換してテープの入力を作るときにtotal recursive functionを用いなければならないとするようだ。*6

It depends on what you mean by "universal". My definition of a "Universal TM" is

there exists a total recursive function which takes a triple (finite alphabet, set of quintuples of a 1-tape TM using that alphabet, initial tape configuration) to an initial tape configuration, such that the "Universal TM" halts if and only if the TM you build from the given quintuples and given tape configuration halts (and both tape configurations have the "blank" character in all but finitely many places).

https://www.cs.nyu.edu/pipermail/fom/2007-October/012125.html

まあ，今回はテープに無限長の文字列を書き込んだものを入力としているのでこの定義は使えないわけだが，例えば，1次元セルオートマトンRule 110の普遍性の（Matthew Cookによる）証明に対する批判は少ないように思う。

  • 1次元セルオートマトンがそもそも両側に無限な文字列の変換規則なので，「無限に並列」な計算能力を持って普通の計算を殴っていると考えることもできる。
  • 左右に十分遠いところでそれぞれ周期的な無限文字列で初期化している。セルオートマトンの規則では，周期的な部分の変換結果は周期的なので，遠いところで周期的なテープに制限すれば，セルオートマトンを（入出力，1 stepでの計算が）有限なsystemと思うこともできる。

Turing machineの場合も，遠いところで周期的な入力テープを与える代わりに，Turing machineのstate数を増やして有限の入力で模倣できるはず。*7ただし，書き換えた後のTuring machineがuniversalなことをもってもとのTuring machineがuniversalとよぶのは良くないかもしれない。（調べるとweakly universalみたいな概念が出てくるし，別の名前でよぶのが良い？）

肯定的なまとめ

  • Wolfram's (2, 3)-Turing machineの動きについて良く調べられていた。
  • エンコードしてparitiesを読み出すことにするのは面白い。

否定的なまとめ*8

  • Wolfram's (2, 3)-Turing machineに無限長の入力をしている。
    • 問題点1. 周期的な入力になっているわけでもなく，入力を作る部分で仮定された計算能力の定義もない。
  • 無限に動き続けるが，ヘッドの位置を見ると現在何回目の模倣をしているかは分かり，それぞれの模倣は有限時間で終わって出力を残す。
    • n回目はcyclic tag systemの実行をn stepsに制限したものを模倣。どれかの回の結果が「停止」なら「停止」が答え。
    • 問題点2. それぞれの出力が「停止」を表しているかを読むのに計算が必要。出力は回を重ねるごとに長くなるが，この計算能力の評価もされていない。

問題点1.のせいで弱い意味でさえuniversalでないかもしれない。どんな意味でuniversalかの定義には問題点2.も解決すべき。

*1:ここでは極めて雑に「模倣 (simulate)」と書いてしまうが，「SがTを模倣する」意味は「Tの停止問題がSの停止問題に帰着できる」こととしておく。何を用いて帰着できるという定義にするかは日記の最後の方で。

*2:この考察を用いて原論文の証明を飛ばした。

*3:gはF2同型。ちなみに，Fourier変換やMöbius inversionっぽくg-1 = gになるが，これはなんて言うんだっけ。

*4:具体的なw, fの大きさも計算されているようだ。

*5:より正確には，十分大きく2wより十分小さい整数nをあらかじめ求めることができて，「最初n回のスキャンでのparitiesがすべて0 (mod 2)になるセット」

*6:あと，tupleの定義は標準的なもののどれかを用い，tupleの定義部分に計算を埋め込むことを防ぐべきっぽい。

*7:2-tape Turing machineを使うのが簡単そう。

*8:文を簡単にするため，「私の理解が正しければ」を省いて断定的に書いた。