発表者：並川淳
日時：11/19 16:00
場所：知識2棟2階セミナールーム
内容：研究進捗状況の報告


アブストラクト：

関数シフトによって生成されるシフト空間の複雑さについて, 
シフト空間の言語が属するクラスの観点から論じる.

最初に, 関数シフトによって生成されるシフト空間の方が, 
元の関数シフトより複雑になる理由について解説する.
次に関数シフトの言語が文脈自由言語, 文脈依存言語, 
帰納的集合, 帰納的に可算な集合(0型言語)の場合それぞれについて
生成されるシフト空間の性質を説明する.

最後に, 関数シフトの言語が帰納的に可算なとき, 生成される
シフト空間の言語が帰納的に可算ではない場合が存在することを示す.
この結果より, 関数シフトは従来の計算論と実数計算論との間の
橋渡しとなる可能性がある.