(旧)計算可能性、距離空間、位相空間
(新)計算可能性、計算複雑度、距離空間、位相空間
「距離空間および位相空間における計算可能性と複雑計算度」というテーマで研究を行なっています。
以下、数学用語が続出しますが、固有名詞だと思って読み流していただいて支障ありません。
ある関数が計算できることを示すには、計算法が発見できれば十分です。しかし、ある関数が計算できないことを示すには、 計算を試みて失敗することでは不十分です。「一所懸命にがんばったのですがダメでした」では、「まだ努力が足りません」や 「やり方が間違っているだけです」を否定できないからです。「計算できる関数」の範囲を明確にして、対象の関数がその範囲に 含まれないことを証明する必要があります。そのためには「計算できる」の数学的な定義が必要となります。こうして、 計算可能性の理論が始まったのでした。
実は、これは、数千年におよぶ数学の長い歴史の中ではほんの最近のことです。最初の本格的は発見は、 1931年のゲーデルの不完全性定理の発見です。それからすこしたった1935年に、チューリングが後にチューリング機械と 呼ばれるようになった仮想的な機械を考えて、理論を精密化しました。そのおかげで、計算可能性の理論は急速に発展し、 コンピュータの基礎理論としての需要もあって、今では、大学の情報系学科では、計算可能性の理論の初歩を学ぶ講義が 学部生を対象に必ず開講されるようになっています。
ところで、計算可能性の理論では、まず、自然数（と有限の長さの文字列）を入出力とする関数を扱います （一般に、学部段階で学ぶのも、この範囲です）。対象を自然数から整数に拡張し、さらには有理数に拡張するところまでは、 同じようにできます。ところが、有理数から実数に拡張しようとすると、それまでと同じようにはいきませんでした。 1954年にライスが「計算可能実数全体が実閉体をなす」ことを発見して、やっと、有理数から実数への溝が乗り越えられました。 計算可能性の理論の誕生から1/3 世紀を要しています。
計算可能性の理論の対象を実数まで拡張できたら、もっと拡張したくなります。複素数への拡張は簡単です。 ベクトルや行列への拡張も簡単です。数だけでなく図形を対象とすることも、ちょっとした技術的な問題を解決すれば、 同じようにできます。
私も、河邑紀子（奈良女子大学、当時）や竹内泉（京都大学）と協力して、計算可能性の理論の対象を平面図形や空間図形に 拡張したものをフラクタル理論に応用して成果を上げています。
ところで、計算可能性の理論の対象をあっちゃこっちゃに拡張するのは良いのですが、対象を新しく考えるたびに毎回、 同じことをするのでは、非効率です。そこで、一般的な、いいかえれば汎用的な理論を構築しておいて、各対象は その具体例という形にしておけば、ぐっと手間が軽減されます。位相空間論というのは、そのためにうってつけの理論です。 そこで、位相空間論と計算可能性の理論を融合させた理論を、私たちは研究しています。
まだ、どんな位相空間でもOKというところまでには達していなく、特殊な場合である距離空間に限定して研究しています。 その中でもさらに特殊な「実効的局所コンパクト距離空間」というものにまでは、鴨?河邑?竹内の手法が適用できることを 証明できました。これをさらに広げることが当面の目標です。