本論文はビジービーバー問題として知られる計算機科学における問題を例にとり、単純な機械に単純な入力を与えた系のダイナミクスとその多様性について力学系の立場から議論する。

　チューリング機械(TM)は計算理論の分野で用いられる単純な計算モデルであり、任意のTMが停止するか否かを判定するチューリング機械停止問題は計算理論の核心である計算可能性を議論する際に重要な役割を果たす。ビジービーバー問題はこのチューリング機械停止問題の一種の変形版であり、次のように定義される。

　TMはテープとマシンで構成され、通常はテープにプログラムやデータなどをあらかじめ記述して、内部に有限状態とその遷移規則を持つマシンがそのテープ上の文字を1文字ずつ読み書きしながら計算を行う。しかしここでは初期テープは空であるものとし、マシンの状態数を限定したうえで遷移規則を適当に決め計算を実行する。すると、あるマシンは何ステップか実行したのちに停止し、また別のマシンは無限ループに陥るなどして永遠に止まらなくなる。このうち最も多くの非空白文字を書き残して停止したマシンを状態数nのビジービーバーと呼ぶことにする。はたして任意の状態数nのビジービーバーを求める機械的な手続きは存在するだろうか？これがビジービーバー問題と呼ばれる問題であり、そのような万能な機械的手続きは存在しないことが証明されている。また、ビジービーバーの書き残した文字数(=スコア)の関数は計算不可能である。

　一般に、計算理論における計算不可能性は万能チューリング機械(UTM)と呼ばれる特殊なTMに対する対角線論法を用いた証明を行って議論されるが、ビジービーバー問題の枠組みでは計算不可能な関数をより直接的に(段階的に)捉えることができ、その性質をコンピューターによる計算実験などを通して定量的に議論できるようになる。そのため低状態数のビジービーバーを探す努力がさまざまな研究者によって行われてきた。しかしながら状態数が増えるにつれてマシンの挙動は複雑化するため手に負えなくなり、わずか5状態のビジービーバーですら現在のところ決定できていない。

　本論文は、このビジービーバー問題に対し力学系の視点からアプローチをとり、計算機実験をとおした計算不可能な関数の統計的性質の検証や、マシンの時空間パターンの分類とその力学的解釈を試みた。

(1)計算不可能な関数についての統計的性質

　ビジービーバー問題ではスコアの他にもいくつかの計算不可能な関数を定義することができる。ある状態数におけるマシンの停止確率もまた計算不可能な関数のひとつである。本研究では、モンテカルロ法などを用いた計算機実験を行い、その結果、停止確率の分布関数は時間経過にしたがい指数分布からべき分布へ、さらに対数分布へと変化することが示された。この結果は斉藤氏らによるUTMへのランダム入力の停止確率の実験の結果と一致するが、より長い時間での分布の詳細を得ることができたので、停止確率の分布はどんな計算可能な関数よりも緩やかになるはずであるという理論的解釈をより端的に裏付けるものである。

(2)時空間パターンの分類と構成比の分析

　状態数の変化に従い複雑化するマシンを特徴付けるため、マシンの位置情報のみに着目し、その時空間パターンにもとづいたマシンの分類を導入した。その結果、高スコアをあげるマシンは特徴的な運動パターンを示すこと、またそのパターンの構成比は時間経過にしたがって変化することがわかった。特に5状態においてはある特定のパターンにのみ収束し、そのパターンを示すマシンの中には現在ビジービーバーの有力候補と考えられているマシンも含まれている。この傾向は10状態程度までにおいて一般的であるようである。

(3)アルゴリズムの力学的解釈

　ビジービーバー問題と3k+1写像として知られる力学系との関連性は既に何人かの研究者によって指摘されている。本研究では、先に導入した時空間パターンによる分類のマシンについてそのアルゴリズムを力学系の視点からの解析を試みた。その結果、長時間において最大多数のパターンに属するマシン群は(確認できた限りにおいては)3k+1写像を拡張した切り替え写像と強い繋がりを持つことが認められ、この性質を利用すれば、現在発見されているビジービーバー候補についての限定された証明も可能になるのではないかと考えられる。また、他のパターン分類に属するマシンについては、いくつかの力学系を組み合わせた干渉による不安定性を利用していることなどがわかったものの、依然として力学解釈の手に負えないパターンも存在する。

(4)2次元ビジービーバー問題

　テープを2次元に拡張した場合での計算機実験を行い、テープに残されたパターンの解析を行った。その結果、1次元の場合とは異なるものの、三角形セルでは多様なパターンの生成を見ることができた。パターンとそれを生成する力学系についての考察はまだほとんど手付かずであるが、一部のマシンについては一次元テープの場合と同様の切り替え写像を使っているものと予想している。

本論文はBusy Beaver(BB)問題をを力学系の問題として考察し、かつその理論的解析を行なったものである。Busy Beaverとは、Turing machineのうち、初期状態がすべて0記号のテープ(以下0テープという)から始めて停止するまでに、最も多く1を書くものをという。Turing machineの内部状態の数を指定して、BBを確定するのは決定不能問題として知られている。

本論文は6章からなる。第1章では、Busy Beaver(BB)問題を紹介・レビューし、その複雑さについて、また力学系の問題としてどう取り扱うかについて詳しく説明している。

第2章では、BB問題の停止問題を議論している。ここでは、0テープから始めて、あるステップのちに停止するTuring machineの割合を、分布関数として計算しその振る舞いを論じている。新しい発見として、停止確率がステップ数の関数として徐々にゆっくりになり、指数型からベキ型に、さらにlog型、loglog型になることが示された。また学位申請者は、吸収壁を持つランダムウォーク模型を使って、この分布関数の振る舞いをある程度まで解析することに成功している。

第3章では、0テープから始めるTuring machineの振る舞いを、Turing machineのヘッドの移動パターンとして解析した。特にBBに近づくにつれて、Turing machineは特徴的な時空間パターンのクラスに落ちることが新しく示された。特に状態数5のTuring machineに関しては、完全に調べ上げている。この結果、semicircle型がBBを特徴づけるという仮説が提案された。この結果はオリジナルで高く評価できる。

第4章では、第3章の仮説を切り替えmodulo関数を用いて解析している。その結果は、BBの振る舞いが別の力学系を使って模倣できることを示唆するもので、今までの数理的解析に道しるべを与えるものとして評価できる。

第5章ではBB問題を2次元のテープを持ったTuring machineの問題へと拡張し、どのような時空間パターンが0テープ(但しこの場合は平面)から出現するかを考察している。これも行田氏のオリジナルな業績であり、高く評価できる。

第6章では以上の重要な結果を順番に簡潔に報告している。

このように、論文提出者は本論文において、BB問題を力学系の問題に帰着させて詳細に解析し、BBの持つ1をたくさん書いて停止するという特徴的な性質を、停止分布関数の変化の中に見いだし、また、modulo関数の切り替え写像系として議論した。オリジナリティーが高く、結果も非常に示唆的で、こうした考察は、計算理論に力学系的視点から新しく考察する糸口を与えたという点で高く評価できる。したがって、本審査委員会は博士(学術)の学位を授与するにふさわしいものと認定する。