力学系の理論と計算理論の整合性を数理的に考察し、両者を統合するような概念を構築する。ここでは以下の3つのトピックを考察した。

　1.)計算の複雑さとフラクタル構造との関連を考察する。

　命題論理式の充足可能性問題(Satisfiability problem,以下SATと表記する.)は数理論理学を背景に持つ代表的なNP完全問題であり、計算の複雑さの理論において実際的計算可能性を考える上で重要な研究対象になっている。ここではSATを例にとり、NP完全問題の幾何構造を数値実験により考察した。具体的にはCNFを次元の単位区間内にコードし,充足可能式をプロットするという方法をとった。結果として得られるパターンは、class Pの問題のとき単純な自己相似集合、class NPの問題のときマルチフラクタルとなることが見いだされた(Fig.1参照)。class Pの問題のパターンについてはその生成系としての縮小写像系が与えられ、Hausdorff次元も解析的に求まった。

図1:右の切断面はclass Pのパターン、左の切断面はclass NPのパターンである。Class NPのパターンは異方性をもつフラクタルとなる。

　2.)高次元力学系が計算を行うためにはどのような力学構造と情報表現が必要になるかを考える。

　切り替え写像系と呼ばれる力学系を用いて、新しい計算モデルを提示した。ここでは力学系のルールをプログラム、軌道を計算の過程ととらえる。軌道の構造は計算過程の構造であり、プログラムの機能に対応する。この枠組により実空間上の計算のダイナミクスを直接構成的に扱うことが可能となり、測度や次元、アトラクタの位相構造といった力学系の特性量を計算論的に解釈することができるようになる。

　切り替え写像系の要素である写像をbaker’s mapにとると、この力学系は古典Turing machineと等価になるが、要素の写像を例えばHenon mapのような2次の非線型性を持つ写像にとると、この力学系はPSPACEの計算能力を持つことが示された(Fig.2参照。)。この計算プロセスを非線型計算とよぶ。極めて微少なノイズにより計算プロセスが完全に破壊されるという意味で、非線型計算は古典Turing machineより不安定な計算であることがわかった。この不安定性のため、非線型計算のプロセスは現実的には実行不可能である。一般に離散力学系は懸垂によって高次元の滑らかな連続力学系に埋め込むことができるが、ここで得た写像系を埋め込んだ高次元の流れ(Computational flow)を考え、この流れの力学構造を解析することを今後の課題と考えている。

図2:量子計算、非線型計算を含めた計算クラスの階層構造の模式図

　3.)ゲーム論理の手法を用いてA.Turingの提示したimitation gameの決定不能性を示し、動的なimitation game、及びnetwork型のN-person imitation gameの枠組みを提示した。Turingの論文にみられる思考実験の代わりにここでは計算機シミュレーションを用いて多人数相互作用系の考察を行った。

　学位論文として提出された佐藤譲氏の博士論文は、力学系の構造と計算理論の枠組を積極的に結びつけることを目的とし、切替え写像系によるモデル化という枠組みの中で、計算機シミュレーションを手法として解析したものである。

　本論文は全5章から成っている。第1章では、研究の目的と動機が簡潔に解説されている。特にチューリングマシンの力学系への埋め込みとその逆の構成について、その分野のレビューを交えながら議論されている。第1章の最後に本論文の中で考察すべき基本的な問いが提示される。

　第2章では、切替え写像系の新しい計算モデルが提案される。2種類のベーカー写像とその逆写像を1つ用いて、チョムスキー階層に対応する計算モデルが構成できることを示した。興味深いのは、ベーカー写像の代わりに2次の非線形性を持つ写像を用いた計算モデルの考察である。ベーカー写像を使ったモデルが、ビット演算を介した古典計算論への翻訳を考えているのに対し、この場合には実数計算に依拠した計算モデルの例をできたことになる。ただしこの場合でも計算能力の程度はP以上NP以下のRPというクラス以下であることが判明した。

　第3章では、N変数の充足可能性問題の恒真式および恒偽式をN次元立方体の内部に埋め込み、埋め込みまれたパターンの形状から充足可能性問題の複雑さを考えるという試みがなされる。特にN＝3の場合はクラスNPに属し、N＝2の場合はクラスPに属することが知られているが、この違いが埋め込みパターンの違いから予測できるという点が興味深い。N＝2の場合が完全なフラクタルパターンをなすのに対し、N＝3ではずれが生ずる。埋め込みパターンを再構成する切り替え写像をうまく構成できたとすると、N＝2では写像の領域が重複しないのに対し、N＝3では領域が重複するために写像の組み合わせ的複雑さが生じ、それがフラクタルからのずれをもたらしているという仮説を提出している。

　第4章では、切り替え写像系と様相論理を組み合わせたモデルを用いてチューリングテストを力学系としてとらえるモデルを提示している。この新しく提案される3人以上のチューリングテストは、参加者が順番に質問を繰り返して相手の「機械らしさ」を考えるというゲームである。したがって参加者が被験者であると同時に判定者である点に特徴がある。具体的には3人のチューリングテストをシミュレートし、他のプレイヤーにとっての別のプレイヤーの「機械らしさ」が会話とともにどのように変遷するかが議論されている。

　第5章は全体の総括であり、「計算の流れ」という視点から力学系のモデルを捉え直していこうという論文提出者の姿勢が再確認される。

　本論文は、計算と力学系をむすびつけて考えよう、という研究の方向を独自の視点からとらえ直したものである。各章はそれぞれ独立した内容ではあるが、論文全体を貫ぬいている、力学系で計算や論理を理解しようという精神は明白である。各章で扱われた問題は一定の決着をつけつつも、その結果浮上した新たな問題点を提起しており今後の研究の発展が期待されるものである。

　以上、当博士論文の研究は、十分に独創的なものであり、力学系と計算や論理との関係を今後考えていく際に、基本となるものをいくつも指し示したといえるだろう。本論文で提案された、力学系を通じて論理や計算の複雑さを考える視点が、第4章の最後にも触れられているように認知科学への発展も含め、広範囲の分野に影響を与えることが期待できる。

　本論文で挙げられた結果のうち第2,第3,第4章の多くの部分が、論文としてすでに専門誌に掲載済みあるいは投稿中である。また共著論文に関しては、それらを博士論文として提出することに関する共著者の同意が得られている。以上のように論文提出者の研究は、力学系と計算と関係の理解に関して独創的かつ重要な寄与をなしていると考えられる。

　以上の点から本論文は博士(学術)の学位を与えるのにふさわしい内容であると審査委員会は全員一致で判定した。