近似プログララムの計算論-古典論理の証明のテストにむけて-

点击翻译按钮获取中文摘要

15年度における近似の計算論に関する研究と、16年度における近似の構成的論理に関する研究を踏まえ、数学・計算機科学における近似の現象を計算の立場から以下の2点に絞って研究した。(1)実数を近似的に表現するするβ展開や、ユークリッド空間上の点を近似的に表現するPisotタイリングなどでは、各数学的対象は唯一の表現を持つが、これらなどを統合的に扱うために、Graph-directed iterated functions systemに着目し、そのアトラクターの要素をそのGIFSが近似的に表現しているものと考えた。この表現系をGIFS-表現と呼ぶことにするが、各数学的対象の表現が唯一である場合は、アトラクター上の実関数で、GIFS-表現に関して計算可能だが局所一様連続でない関数があることを証明した。一方、タイリングから自然に、準結晶の数理モデルである切断射影集合が現れるが、切断射影集合は概周期関数を近似するのに用いられる離散集合であるが、その対称性と双対性に関する研究を行った(2)近似の計算論を研究していたときに近似の収束の速度に興味を持ったが、まず、関数の学習対象とする計算論的学習理論において、近似の速度に関するCase-Smith階層に着目した。計算論的学習の動機として、コンピュータウィルスの振舞からウィルスのシグナチャの学習や、ネットワークを通して計算機を適応的に管理するというところに動機を求めた場合、学習の条件としてGoldが導入した学習の無矛盾性が重要になることを認識した。Goldの無矛盾性を弱めてもやはりCase-Smithの階層が崩壊することを示した。