欲求段階説と強化学習

マズローの欲求段階説 (Maslow's hierarchy of needs) を強化学習の視点から検討してみる。

注意：この日記を信じて機械学習や心理学などの理論を誤解したとしても責任はとれません。ポエムなので。

1. 生理的欲求

環境が返している報酬はこれ。immediate rewardで教師あり学習してもそれなりになりそうということ。

2. 安全欲求

どうやら，価値関数を学習しはじめたようだ。Bellman equationを満たそうとする試みがこれだ。

3. 社会欲求

環境がmulti-agentになったぞ。そうだ，環境の状態遷移は「他者」の行動にも依存している。

4. 承認欲求

さらにcommunicationを学習に使うようになった。他者の承認と比べて自己承認は難しく，振動などしがち。

5. 自己実現欲求

学習を助けるために導入されたはずの正則化が煩悩となる。個性と言えば聞こえは良いが，もとの環境にfine tuneできてないだけでは。

(6. 自己超越欲求)

どうみても発散です。本当にありがとうございました。

まとめ

「下位の欲求の方から満たされる」という主張は学習の難易度でわりと説明ついてしまわないか。「欠乏欲求を十分に満たした経験のある者は」といった主張とも整合的だ。

「アカとブルー」を通しクリアしたのでとりあえず弾幕STGについて思うところを書く

タノシマスの「アカとブルー」が超面白かった。
http://tanoshimasu.com/aka-to-blue/

まさか，2017年にケイブシューの新作が遊べるとは思わなかった……いや，まあ，厳密にはケイブ辞めた人が作った弾幕STGなんだけど。とにかく，どのあたりが感動ポイントなのかは伝わりにくそうだし，良い機会だから私が遊びたいゲームの条件みたいなことから書いてみる。

ゲームに求める「求められたいもの」

ゲームやってて「上手くなったなー」と思うときが楽しい，という派閥だと思う。そう仮定して，何を上達するのが楽しいのか。ぱっと思いつくのは以下の3つ。

認識

音ゲーの用語では，流れてきた譜面すべてを把握できること。より一般に，ゲームをどれくらい理解できているか，という側面。STGの場合上手くなると，自動車のベテラン運転手と同様に，敵や弾に正しく注意を払えるようになるような気がする。

あるいは，認識に必要なリソースをいかにして減らすかということ。音ゲーだと4分バスを自動化するとかの話。STGだと自機狙いを無視してランダム弾だけ見るとか，弾の列の先頭だけ見るとか。

判断

どのリスクをとるか選ぶこと。STGでは

  • way弾の間に入るか，全体を大きく避けるか
  • 前に出て速攻するか，下がって避けに徹するか
  • 軸ずらしをいつ切り返すか
  • ワインダー2列同時にくぐるか1列ずつくぐるか

など。判断によって何を認識すべきかは変わるし，そもそも

  • 自機近くを注視するか，高速弾の着弾位置の予測をするか

という選択自体が判断と言ってよい気がする。

計画

パターン構築のこと。その場で判断できるようになるのも楽しいが，その場で判断しないで済む方法を考えるのはもっと楽しい。

今，詳しく書くと「アカとブルー」のパターンのネタバレをしてしまいそうなのでSTGのケースは省略。音ゲーの運指（の崩し方），パズルゲームの積み方（ぷよぷよの階段積みとか鍵積みとか）。

なぜ今時，弾幕STGをやるのか

「要するにプレイヤースキルが大事なゲームが好きなんでしょ」と言われたら困ってしまうが，あえて付け足すなら，弾幕STGはここで挙げた認識・判断・計画の3要素をバランスよく要求してくるのが好きだ。（他のゲームジャンルがそうでないとは言っていない。）

だいたい，認識が自明なら「計算問題」になるし，判断が自明なら「楽器演奏」になる。そして，計画が自明なら「職業訓練」ではないか。

攻略情報がすぐに出回る時代だけど

話を戻して，「アカとブルー」について。何が良かったかを一言で言うと，自力で攻略する経験ができたこと。

単純に「ネタバレを踏まずに済んだ」という意味では，配信直後に遊べたというのが大きい。冗談みたいな初見殺しにすらきっちり引っかかり，それを次に直すだけでも進捗を感じてモチベーション維持になっていた。

それに加えて「挫折させられるくらいに大きな壁がなかった」のが幸運だった。つまりは，ゲームの難易度要素の分布が自分のスペックと相性が良かった。具体的には，

  • 面クリア制なので長時間の集中力は要求されない
  • 弾道が曲がらないので認識しやすいし後から考えやすい
  • ボムがストック制ではなくハイパーみたいなあれなので遠慮なく撃てる

みたいな感じ。スマホでも一応遊べる調整のはずのものをiPadで遊ぶことで気合避けの下手さを補えたという話もある……。

これまでに遊んできた弾幕STGの中での「アカとブルー」の立ち位置

弾幕STGとの出会いは例によって東方シリーズ。永夜抄が詠唱組でnormalクリアできたくらいで，紅・妖・永・風・地とやってて他はeasyクリアのみ。あまり上手くないまま去ってしまったようなバックグラウンド。

その後，機会があってRebRankの五月雨を遊んだ（Extraの3面に入るところまでくらいやった）ことがあり，それとは別にカタテマのムラサキを遊んだら実はSTGだった（6面は投げた）のが「第2期」。今が「第3期」で，ゴ魔乙を始めたのをきっかけに，怒首領蜂一面番長をひと通りやって，ゲーセンで最大往生をやったら全然無理で（当然だ‥‥），そんな頃に大復活のsteam版が出たのでアケコンを買って家で練習しているところ。

整理しよう。

適当に遊んでいてもクリアできてしまったゲーム
  • 東方シリーズのeasy
  • ゴ魔乙（※スコアタは考えることが多い）

必要な知識は，奇数弾・偶数弾くらい。東方のeasyボスは「大きく誘導するだけ」とか「大回転するだけ」とかがあるのでそれらも知っているとなおよし。知識さえあればあまり考えなくてもクリアできてしまう。

早々に攻略情報を見たがクリアできなかったゲーム
  • 東方シリーズのnormal以上（※永はマリス砲のおかげなので除外）

結局，どのスペルカードをボムで飛ばすかくらいしか工夫できなかった。それでも，気合避けがかなり要求された覚えがある。

それなりに自力で攻略が進んだがクリアできなかったゲーム
  • 東方シリーズのextra（の道中）
  • 五月雨
  • 一面番長
  • 大復活（1周）

弾幕STGに興味を持てているのはこのあたりのおかげ。全クリできてないせいで達成感が得られてないけど，それでも面白い。下手くそがSTGについて語るなよみたいなことは言わないでください。

自力で全クリできたゲーム
  • アカとブルー

ということで，今回，初めてこの枠ができて，めでたしめでたし。

「アカとブルー」楽しみました

やばい，結局「アカとブルー」とあまり関係ない話ばっかり書いてた。まとめにくいので，時系列で回想しておしまい。

開発中の話はそこそこ前から聞いていて，配信開始を半年以上待っていた。配信開始は8/10でその日の夜に買って，8/11–13の連休の大部分をつぎ込んだような……。

ゲームのメカニクスの外，たとえば

  • 道中の会話ボイスで話が進むのが良かった
  • こんなに弾とアイテム描画して処理落ちしてないのすごい

なんかも良かった。このあたりの感想は他の人も書いているだろうしパス。

設定
  • 操作感度：等倍（スライダーど真ん中）
  • 自動座標補正：なし（スライダー左端）
  • オートボムOFF（最初のバージョンではOFFがデフォルトだったが，今のバージョンではONになっているらしい？）
8/11（金祝）

1面は数回の試行ですんなりクリアしたはず。まあ，これくらいの弾幕STGの基礎知識はもともとあったということ。

2面はボスで苦戦した。気付いたら被弾してたみたいなことが多く，ボスの弾幕パターンの認識・理解の必要性を感じていた。

3面は道中が難しかった。この頃は，ボムの挙動は分かっていたけど良い使い方を分かっていなかった感じ。なかなかボスまで到達できなかったため，ボスの弾幕の避け方をあらかじめ考えておく作戦になった。

アカ・ブルー両方の自機でここまでクリアして初日は終了。

8/12（土）

4面を頑張った日。4面は開幕から難しく，「この調子で難しくなるんだったら，自分には全クリできないのでは」という気持ちが強かった時期。

苦手ないくつかの区間についてパターン構築した。「自機狙いが来たら左に避ける（右手で操作していて右側が隠れがちなので）」みたいな手癖で不味いことになる場所を修正するのから始まり，結局，注意すべき敵の出現順を完全に覚えることになってしまった。

ボスの弾幕を全然理解していなかったため，「道中を無被弾にして，ボスは気合避けとボム」みたいな攻略になってしまった。なんか運良く気合避けが通ってアカでクリア。

4面道中で決めボムが上手くなったような気がする。

この日はブルーではクリアできず。だって，ブルーのボムの発射方向の制御に気を取られて死ぬし。

8/13（日）

5面。

中ボスがやたら強くて，ボスにたどり着くのが限界。

8/14–17

連休中にクリアするあてが外れてしまったが，その後も毎日ちょっとずつやってた。5面やりつつ，前の面の稼ぎっぽいのとかノーミスとかノーボムとか。

アドリブで避けたりボムを適切に撃ったりする力もついてきて，「適当にボムったら詰んだ（自分にはできない気合避けを要求された）」みたいなのを覚えていく感じに。

中ボス戦は練習の結果かなり上手くなった（【ネタバレ削除】が【ネタバレ削除】で【ネタバレ削除】も分かった……）一方，ボス戦は全然理解できてなかった。

とはいえ，ボス到達回数が増えるとともにいくつかの作戦を検証できて，弾幕ごとに勝ちやすい作戦を実行したら何とかなった。ボス発狂到達2回目でクリア。発狂については1回目の挑戦で何が悪かったか分かったのでウィニングラン。

8/21

ブルーで4面と5面をクリア。

4面ボス，5面ボスの発見は増えた。中ボスは攻略しつくした感もあったが，完璧からは遠かったのでパターンの改良を余裕のあるとき（というより，道中被弾して捨てゲー気味なとき）に調べていた。

ブルーでの5面道中はアカの場合のパターンが微妙にはまらない箇所が結構あってパターン作り直し。

エピローグ部分，自機がアカでもブルーでも同じなのね……。

8/24–25

スコアタにも力を入れようかと思って得点条件を調べようとしたが，よく分からない。得点アイテムを取ったときだけでなく，敵の撃墜でも点が入っているように見える。「こういうのは動画撮らないと無理なのでは」と思って諦める。

4, 5面の勝率が上がってきたので全5面通しクリアを目標に。

4面開幕2被弾からクリアとか，5面ボス発狂まで行ったのに死亡とかいろいろあった。2, 3面も練習してないと危ない。

8/26

アカで通しクリア達成。演出は何もなかったような気がする……。クリア後，ステージセレクトの画面に戻ったときに，（5面ではなく）1面が選択された状態になっているほうが良いのでは。

ブルーの通しクリアはまだできてない。なんか，5面道中が安定しない。雑魚編隊の体当たりが凶悪な気がするんですが。

8/27–29

この日記書いてた。

補足

ゲームデザインの話じゃない

ゲームで上達したい要素について書いたことは，あくまで，ゲームを遊ぶ側の心構えについての一案。作る側，ゲームデザインにおけるゲームの「要素」の話はゲームデザインの専門家にどうぞ。

精度について

ゲームの場面・区間ごとにそれぞれ8割勝てるという技量になっても，そこから，それぞれ99%勝てる技量に引き上げようとすると新しい発見がある。操作精度を上げるだけでなく，パターンの組み直しが必要なこともある。これは面白い。

しかし，100点満点中100点をとる目標のゲームは厳しい。出来たときの達成感はあるけど。具体的には，音ゲーでフルコンボとか全Perfectとかを目指すのは辞めてしまった。音ゲーに限らず，合格ラインの高すぎるゲームは「攻略の幅が狭い」問題がありがちに思う。

それより「小さいミスの後，いかにリカバリーするか」というゲーム性の方が好き。「残機3固定でその場復活のゲーム」では一見100点満点中98点をとる目標になってしまうと思いきや，「アカとブルー」はボムが強くてリチャージもあるのでクリアに必要な合格点はかなり低い。（不用意にチャージ1以下になるのが「小さいミス」。）

マリオメーカーのTuring完全性

ここ最近Turing完全性などに（細かい部分も含めて）興味を持っていたのは，実は，そー氏*1のマリオメーカー*2研究がきっかけでした。今日公開された動画にちょっとだけ協力していたので宣伝します。

マリオメーカーはチューリング完全だった【万能計算機】
D

私はマリオメーカーについては素人で，計算コースの実装とかはできないのですが，確か，そー氏によって「最初の証明」*3のステージが作られたくらいのときに

  • 「Rule 110の完全性を用いているけど，その『有限』だとまずくない？」
  • 「Cyclic tag systemならすでにある（そー氏がマリオメーカー学会で発表済みの）テクで実装できるのでは」

みたいなことを伝えたら，数日しか経たないうちに「真の証明」のステージが返ってきたという……。

*1:っていうかyos

*2:マリオの自作ステージが作れるWii Uソフト

*3:動画中での呼び方

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:文を簡単にするため，「私の理解が正しければ」を省いて断定的に書いた。

1次元3状態2近傍セルオートマトン

Processingで遊んだ。



















今回の設定で考えられるルールは332=19683通り。鏡映と色の入れ替えで同値なものを除くとたぶん1734通り。4状態にすれば2状態3近傍のルールを埋め込めるので，Turing完全なものがあることが（Rule 110の完全性から）分かるが，3状態でできるのだろうか。

キーを押すたびにランダムなルールに更新されるようにしたのでガチャが楽しめる。日記を書くにあたって追加20連ガチャ：

  • N：単色
  • R：3色，真下に周期的
  • N：2色，右下に一定
  • N：3色，右下に周期的
  • N：2色，右下に一定
  • N：2色，右下に周期的
  • N：3色，右下に周期的
  • N：2色，右下に周期的
  • R：2色，カオス
  • SR：3色，カオス，ある程度の単色領域もある（上に貼った中で2番目みたいなの）
  • N：2色，右下に周期的
  • N：3色，右下に周期的，同色が繋がっていて楽しい（上に貼った中で13番目みたいなの）
  • R：2色，カオス
  • N：単色
  • N：3色，左下に周期的
  • R：3色，下寄りの右下（3列で半マスずれる）に周期的
  • R：3色，左下にのびる1色と右下にのびる1色が対消滅
  • N：3色，左下に周期的
  • N：2色，左下に周期的
  • N：単色

Rule 110について（前編）

1次元セルオートマトンのRule 110がTuring完全と聞いて。

Tag system

まずCocke, John, and Marvin Minsky. "Universality of tag systems with P=2." Journal of the ACM (JACM) 11.1 (1964): 15-20.を読んだ。

そもそも，tag systemとは，文字列書き換え規則であって，「先頭P文字を消し，そのうちの1文字目にのみ依存して末尾に何文字か加える」ようなもの。これを繰り返して特別な文字が先頭に来たら停止。

さて，2-symbol Turing機械をP=2のtag systemで模倣するのだが，今回は計算可能性しか考えていないため指数爆発しても良い。具体的には，ヘッドの左右を2進法で読み（ヘッドに近い方が下の桁，十分遠くでは0が並んでいるので良い），その回数の文字列の繰り返しとして符号化する。

例：… 0 0 0 0 1 1 0 q 1 1 0 1 0 0 0 0 … ↦ Ax(ax)6Bx(bx)11 = AxaxaxaxaxaxaxBxbxbxbxbxbxbxbxbxbxbxbx *1

Turing機械がヘッドを左右に動かすことは文字列の繰り返し回数を2倍や1/2倍にすることに対応するので，「2文字消して4文字書く」とか「2文字消して1文字書く」とかいった方針でtag systemでも頑張れる。

Turing機械がテープを読み取るのは文字列の繰り返し回数を2で割った余りに対応するが，それによる条件分岐も実はtag systemで書ける。だいたい，

  • a2n → … → (bc)n → … → (hoge)n
  • a2n+1 → … → a(bc)n → (cb)nc → … → (fuga)nc

みたいにすれば良い。

Cyclic tag system

ここからtag systemをcyclic tag systemで帰着して，さらにgliderの何かに帰着し，Rule 110がそういう適切な性質を満たすgliderを持つことを示す流れのようだ。

セルオートマトンで最終的に模倣したいのだから，まず問題になりそうなのはtag systemで何種類の文字が使われるかに制約がないこと。Turing機械についてテープ文字集合が {0, 1} の2文字である場合に帰着するのは簡単だが，tag systemについて文字集合の大きさを2に帰着するのは上手くいかないように思える。

それが理由でかどうかは知らないが，文字列の書き換え規則を固定周期で変化させるようにすると，2-symbolな"tag system"に帰着できる。おまけにP=1にできて*2，しかも文字0の変換先を常に空文字列としても十分で，これをcyclic tag systemとよぶ。

実際，k-symbolのtag systemに使われる文字それぞれをcyclic tag systemでは「1箇所だけ1で残りk-1箇所が0の長さkの文字列」で模倣する。ただし，tag systemの停止文字をcyclic tag systemの停止文字としては模倣できていないことには注意が必要そう。

*1:正確には，状態 qi ごとに別の文字 Ai, xi, ai, … を用いる。

*2:もとのtag systemはP=1では文字列中の文字の出現順序にまったく意味がないため，「文字間の（非決定的）遷移規則」とみなしたときの到達可能性を調べる程度の計算能力しかない。

自由意志を考えるときのメタレベル

  • ナイーブには自分に自由意志はあると思う。
  • 唯物論を信じている。
  • 唯物論を仮定すると誰にも自由意志はないと結論できるような気がする。

これらは矛盾するように見えがちだけど，そうでもないよね。

「『自分が信じている世界』の中にいる自分」は対象化されていて，自己言及のパラドックスがおきるような本当の「自分」ではない。自分の中に作られた「唯物論を満たす世界」は本当の「世界」をよく真似ることができることを経験的に知っているが，それが正しいのか，どこまで同一視できるのか，よく分からないような気がする。

有限的な手続きしかできなくても，無限集合（非可算無限さえも）が扱えるように。適当な算術が「有限的な手続き」を表すと考えられているが，その考え方自体は証明すべきものではないように。