オートマトンの受理集合・判定手続きによって定義される幾何集合・力学系のベイシンは、全て判定手続きによって定義される。これらの集合はそれぞれ計算論・幾何学・力学系研究という異なった分野で扱われ、集合の要素も異なるが、判定手続きによって定義される停止集合という意味においては区別ができない。しかし、その共通点に注目して、これらの集合を統一して研究することは、これまでなされてこなかった。本論文では、これらの停止集合の幾何的性質と判定手続きの力学系的性質を同一の手法を使って研究する(オートマトンの受理集合の場合には、シンボル列をEuclid空間上の点にコードすることによって幾何的・力学系的性質を研究する)。

　具体的に、判定手続きによって定義される停止集合として、万能Turing機械の停止集合・Mandelbrot集合・riddled basinを対象に研究を行なう。これらの集合は、単に判定手続きによって定義されるというだけではなく、受理集合・幾何集合・ベイシンの中でも最も複雑なものとして知られている。また、単純に自己相似性だけでは特徴づけられない、非自己相似集合でもある。停止集合の幾何的性質としては主に境界次元、判定手続きの力学系的性質としては停止時間の分布を調べる。その際、非線形力学系研究で使われる実験的手法を積極的に用いる。

　2章では、コードについて調べる。オートマトンの受理集合の幾何的性質と判定手続きの力学系的性質は、一般に、シンボル列をEuclid空間上の点に対応づけるコードに依存する。本論文では、シンボル無限列を区分線形写像のマルコフ分割の同じラベルで指定される実数に、シンボル有限列を同じラベルで指定される区間に、それぞれ対応させるコードを扱う。このようなコード全体を考えた場合、あるコードから他のコードへの変換はLebesgueの特異関数のようなフラクタル関数になり、一般に(境界)次元の値を保存しない。

　3章では、特に決定不能性がどのように特徴づけられるかに関心を持ち、万能Turing機械の停止集合を扱う。決定不能性は古典計算論では最も重要な概念であり、決定不能集合(帰納的加算言語)はChomskyの階層の中でも最も複雑なものである。この対象に対して証明という従来からの手法のみを使うのではなく、実験的手法を積極的に用いて研究を行なう。2章で導入したコードを用いて、万能Turing機械の停止集合をコードした幾何集合は、任意の小さなスケールで異なった構造を持ち、また、異なったパターンを持つことが分かる。

　さらに、万能Turing機械の停止集合の境界のbox-counting次元に関しては以下のことが分かる。万能Turing機械の停止集合に含まれる初期点の内、ある有限の計算時間n以内に停止する初期点を2次元平面上に埋め込んだ幾何集合について、その境界次元を数値的に調べた結果、計算時間nの増加とともに境界次元はコードした空間の次元である2に漸近して行く。特に、計算時間nの極限で定義されている万能Turing機械の停止集合の場合、その境界次元は空間次元の値2と等しくなることが分かる。さらにこの結果は、フラクタル変換であるコード変換に対しても不変であり、コードには依存しない。

　境界次元が空間次元と等しい場合とそうでない場合とでは本質的な差がある。境界次元が空間次元と等しいことは、境界の近傍を考えた場合、その体積(面積)がに依存しないことを示している。それはつまり、観測精度の誤差の存在下で、万能Turing機械の停止集合に含まれるか否かを判定する場合には、観測精度をいくら上げても原理的に誤る確率を下げることができないという強い不確定性を意味する。判定手続きに関していえば、例えどんなに小さくても誤差が存在する限り、誤差なしの状態で定義された判定手続きのモデルには近づけないことを意味する。このモデル到達不可能性は、決定不能性がカオス的初期条件鋭敏性とは異なり、観測精度に関係なく存在することと対応する。この様に、万能Turing機械の停止問題の持つ決定不能性は、モデル到達不可能性、および、この性質のコード変換に対する不変性によって特徴づけることができる。

　同様に、万能Turing機械の停止時間の分布が、時間nに対して、ベキ的(またはそれより緩やか)に減衰すること、また、この性質がコード変換に対して不変であることも分かる。

　4章では、特に万能Turing機械の停止集合との類似性に注目して、幾何集合であるMandelbrot集合を扱う。Mandelbrot集合は単なる自己相似構造ではなく、極端に複雑な構造を持つことで知られており、その境界のHausdorff次元が空間次元と等しくなることが証明されている。これまでにも決定不能性との関係に関心が持たれ、実数計算モデル方面からの研究がなされたが成功しているとはいえない。

　Mandelbrot集合に対しても、万能Turing機械の停止集合と同様に、境界次元の計算時間に対する漸近的な振る舞いと判定手続きの計算時間の分布とを調べた結果、コード変換に対応するフラクタル変換に対する振る舞いも含めて、万能Turing機械の停止集合と同じ性質を持つことが分かる。このことは古典的な意味での決定不能集合と同等の、モデル到達不可能性、および、この性質のコード変換に対する不変性を持つことを示している。この様に、Mandelbrot集合と決定不能集合との関係を明確な形で明らかにする。

　5章では、riddled basinを扱う。riddled basinを持つ力学系は、初期点が最終的にどのattractorに収束するかに関しても誤差存在下で予測不可能になるという意味で、一般的なカオス力学系とは質の異なった不確定性を持つ。

　ある簡単な力学系のriddled basinは、ある文脈自由言語ををコードした集合になることが分かる。境界次元に関しては、上記の万能Turing機械の停止集合やMandelbrot集合の場合とは大きく異なり、たとえ、このriddled basinの境界次元が空間次元と等しくなった場合でも、コード変換によって簡単にこの性質が壊れることが分かる。同様に、停止時間の分布に関しても、コード変換によって性質が変化することが分かる。この様にこのriddled basin(文脈自由言語)は一般的なフラクタル集合と上記の万能Turing機械の停止集合やMandelbrot集合の中間に位置する。単純に自己相似性だけでは特徴づけられない非自己相似集合、特に境界次元が空間次元と等しくなる集合の中にも様々なクラスが存在することが分かる。

　以降、6章では、修正を加えた(万能)Turing機械の停止集合の幾何的性質と判定手続きの力学系的性質ついて、特に加えた修正と計算万能性との関係に注目して調べる。7章では、この論文で得られた結果に基づいて、実数計算とコードに関して議論する。

　提出された斉藤朝輝氏の博士論文は判定手続きによって定義される集合の幾何学的、力学系的性質を研究し、特に、計算理論での決定不能性を持つ集合の満たす特性を明らかにしたものである。

　ここ10数年、計算理論と力学系を結びつける試みがいくつかなされ、その中には決定不能性をカオスのような予測不能性と異なるダイナミクスとして捉えようというものがあった。しかし、決定不能性と力学系的/幾何学的性質を結びつける明確な言明は未だなされていない。斎藤朝輝氏の博士論文は、計算理論でのオートマトンの受理集合と力学系のベイシンがともに判定手続きによって定義される集合であるという共通点に着目し、これらの集合を統一的に研究することで、上記の課題に対してひとつの解答を与えるものである。具体的には、万能Turing機械の停止集合・Mandelbrot集合・riddled basinを対象にし、それらの持つ境界次元と停止時間の分布によって、決定不能性が特徴づけられている。

　本論文は7章から成っている。まず第2章では、この研究を行なう上で幾何的性質と判定手続きの対応づけを行なうためのコード化が導入される。次いで第3章では、決定不能性の普遍的表現として、万能Turing機械の停止集合が調べられる。その幾何学的性質として、万能Turing機械の停止集合をコードした集合が、任意の小さなスケールで異なった構造を持ち、また、異なったパターンを持つことが着目される。その定量的表現として、万能Turing機械の停止集合の境界の次元が数値的に調べられる。その結果、境界次元が時間を増して行くにつれて空間次元2に漸近することが示され、またその理由も述べられている。この性質はカオスで見出されるようなベイシンのフラクタル構造(その場合は空間次元より境界次元が小さくなる)とは異なったものである。さらに、こうした集合は観測精度の誤差の存在下で、それに含まれるか否かを判定しようとすると、観測精度をいくら上げても誤る確率が下げられないという、強い不確定性を有することが指摘され、これを論文では到達不可能性と呼んでいる。この到達不可能性は、決定不能性が観測精度に関係なく存在することと関連すると考えられる。さらに、万能Turing機械の持つこの性質は(適当な範囲の)コード変換に対して不変であることが数値計算を通して確認される。

　ついで、万能Turing機械の停止時間の分布が、時間に対して、広い範囲でベキ的に減衰することが示される。決定不能性の性質から、この性質は時間無限まで続かないことが予想されるが、この広い範囲でのベキ的振る舞いは、予想されなかった、未だ説明のついてない新しい発見である。

　4章では、特に万能Turing機械の停止集合との類似性に注目して、幾何集合であるMandelbrot集合を扱われる。Mandelbrot集合は通常の自己相似構造ではなく、次元が2となるような複雑な構造を持つことが証明されており、決定不能性との関係にも関心が持たれてはいたが、明確に関係づけられずにいた。このMandelbrot集合に対して、境界次元の計算時間に対する漸近的な振る舞いと判定手続きの計算時間の分布とが数値的に調べられている。その結果、コード変換に対応する変換不変性も含めて、Mandelbrot集合が万能Turing機械の停止集合と同じ性質を持つことが示されている。これはMandelbrot集合と決定不能集合との関係を明確な形で示すことに成功したものである。

　5章では、riddled basinが扱われている。riddled basinを持つ力学系は、初期点が最終的にどのattractorに収束するかが誤差存在下で予測不可能になるという意味で、カオス力学系とは質の異なった不確定性を持つことが知られている。簡単なriddled basinを持つ力学系について数値計算および解析的計算の結果、境界次元や計算時間の分布が(決定不能性を持つ)万能Turing機械の停止集合と同じ性質を持つことが見出される。しかし、この場合、この性質はコードの変換に不変でないことが示される。今の力学系は計算理論では文脈自由言語を持ち、一般的なフラクタル集合と決定不能集合の中間に位置すると予想されるものである。コード変換による変化という形で、この計算理論での「中間的」性質が幾何学的/力学系的性質として表現されたことになる。これらの結果をふまえ6、7章では、コードの問題や実数計算論などの一般的な問題が議論されている。

　以上、当博士論文の研究は、計算理論に対して、力学系の視点から新しい特徴づけを提示したものである。特に、境界次元の空間次元への漸近と決定時間のべき分布、それらのコード不変性という性質によって、計算理論から力学系での決定不能集合を統一的に特徴づけたことは新しい大きな成果である。この結果がどれだけ計算過程自体に意義を持つか、またここで見出された性質を厳密に証明できるか、など今後研究されなければならない点も残っている。しかし、ここで提出された切口は基本的で独創的なものであり、また実数計算論のような非標準的計算理論にも将来示唆を与えうると期待される。

　当研究は計算理論、非線形力学系への理解を基盤として数値計算と理論的考察により完成したものである。ここで挙げられた結果の一部の速報は既に専門誌に掲載されており、その全貌は間もなく投稿予定である。このように、論文提出者の研究は、計算理論、非線形力学系について新しい方向を切り開いたものであり、計算理論、力学系分野への独創的かつ重要な寄与をなしていると考えられる。

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