December 11(Saturday)
10:00-10:50 T. Mori: Effective convergence of Fine computable
functions
11:00-11:50 V. Brattka: The Hahn-Banach Theorem and its Impact on
Computable Analysis
12:00-12:50 S. Hayashi: LCM and games
13:00-14:30 Lunch
14:30-15:00 Free discussion
15:00-15:50 P. Hertling: Topological Complexity of Zero Finding for
Continuous Functions
16:00-16:30 Free discussion
16:30-17:00 Clearing
December 12(Sunday)
10:00-10:50 M. Yasugi: Effective sequence of uniformities
11:00-11:50 P.Hertling: Is the Mandelbrot set computable?
12:00-13:00 Lunch
13:00-13:50 T. Yamazaki: Some results on higher order reverse
mathematics
14:00-14:50 A. Yoshikawa: Questions and problems from a naive observer
of the field
15:30-16:30 H.Kamo: Computability of Urysohn's Universal Metric
Space
16:30-17:00 Clearing up
にあります。
研究代表者 八杉満利子 分担者 ９名
研究種目 基盤研究 （B) （２）
課題番号 12440031
＊関連研究会等
第一回ＣＣセミナー
７月２２日（土曜日）
0:40-11:00 八杉 連続体上の計算可能性問題と、研究目的
11:00-12:00 吉川 Besicovitch 被覆定理に内蔵されるアルゴリスム構造 とその実解析における意義
14:00-15:00 立木 拡張された文字列への実数の埋め込みと計算可能性
15:10-15:40 森 Walsh 関数系の計算可能性について
16:00-17:00 小田・岩崎 Simulation cheap-talk games
７月２３日（日曜日）
10:40-11:10 山田 Repetition free sequences
11:30-12:00 中田 Limiting Recursive Function によるrealizability interpretation
14:00-14:30 林 Some problems of Limit Computable Mathematics
14:50-15:20 鷲原 シュワルツ超関数の空間と計算可能性
15:30-16:00 自由討論
場所： 京都産業大学・第一研究室棟・第二会議室
第二回ＣＣ−セミナー
日程 ２０００年１２月１６日（土曜日）、１７日（日曜日）
詳細はプログラム参照
場所 （財）京都市国際交流協会 KYOTO CITY INTERNATIONAL FOUNDATION
所在地 〒606-8436 京都市左京区粟田口鳥居町２-１
TEL（075)752-3010 FAX（075)752-3510
http://www.kcif.or.jp/
Program
12/16/(Saturday)
10:00-10:10 business communication
0:10-11:10 Brattka, Vasco An approach to computable linear algebra
11:30-12:30 Hata, Masayoshi Rational approximations to $\pi$
Lunch
14:30-15:30 Yoshikawa, Atsushi The inviscid Burgers' equation and computability
16:00-16:30 Washihara, Masako & Takamuki, Ryoji Computability and functions of bounded variations
16:00-17:00 Free discussion
12/17 (Sunday)
10:00-11:00 Ishihara, Hajime Sequential continuity in constructive analysis
11:20-12:20 Brattka, Vasco Recursive quasi-metric spaces
Lunch
14:20-15-10 Hayashi, Susumu Relations between BSS machines and LCM
15:00-16:00 Tsuiki, Hideki Computational dimension of the topological space
16:00-16:30 Free discussion
Clearing up
17:00 Closing
科研費(No.12440031)によるセミナーを開催します。 皆様のご参加をお待ちします。
講師：Peter Hertling氏（Fernuniversitaet Hagen）
演題：Left-computable random numbers
日時：２００１年２月１７日（土曜日）１０：００−１２：００
場所：（財）京都市国際交流会館
KYOTO CITY INTERNATIONAL COMMUNICATION HOUSE
所在地
〒606-8436
京都市左京区粟田口鳥居町２-１
TEL（075)752-3010 FAX（075)752-3510
http://www.kcif.or.jp/
地下鉄東西線蹴上げまたは市バス５番神宮道より徒歩数分。
連絡先：京都産業大学理学部 八杉満利子 yasugi@cc.kyoto-su.ac.jp
Abstract:
In 1966 Martin--Loef introduced an algorithmic randomness notion
which makes it possible to speak of individual random binary sequences.
This notion can also be characterised via program size complexity
following Kolmogorov and Chaitin. The talk will start with
an introduction into these notions. Then we will focus on
recent results about a special class of random binary sequences
or random real numbers, the so-called Omega numbers.
These are prominent random real numbers which were introduced
by Chaitin in 1975. But only recently it has turned out that
the class of Omega numbers coincides with the class of
so-called Omega-like numbers introduced by Solovay also in 1975,
and, even more striking, it coincides also with the class of
left-computable random real numbers.
講師：高橋 大輔 氏 （早稲田大学）
演題：構造の抽出と離散化---超離散化の試み
日時：２００１年３月１６日（金）１４：００−１６：００
場所：京都産業大学第一研究棟、第２会義室
連絡先：京都産業大学理学部 八杉満利子
yasugi@cc.kyoto-su.ac.jp
アブストラクト
最近，超離散化と呼ばれる手法によって微分方程式・差分方程式・セル
オートマトン間の直接的なつながりがあきらかにされつつある．その手法
は今のところ汎用的なものではなく，方程式や解に存在する数理構造の表
現を連続から離散，離散から連続に変換するという形をとっている．この
ため，連続離散の一方の世界で見えなかったものが，もう片方の世界で見
えるというような面白いことも起こる．このような超離散化の手法に
ついて具体例をたくさん引き合いに出しながら解説を行う．
基盤研究（Ｂ）
抽象空間における計算可能性構造の理論および型２マシンの理論を中心に、数学の種々な
オブジェクトの計算可能性に関してほぼ予定通りの成果を得た。描画は精度の問題があって、
未完成である。主な結果は次のとおりである。１ 一様位相空間における計算可能性構造：
整数点などでジャンプするが残りの各開区間で連続な実数値関数などは不連続ではあっても
計算の意味をもつ。その現象の数学的な基礎づけのために一様位相空間における計算可能性
構造を導入した。すなわち、定義域を関数が連続な部分と不連続点とに分離してそれぞれに
位相を導入し、それらを合併した新しい一様位相空間とみなした。そこにおける関数の計算
可能性などを定義し、多くの例および反例を与えた。２ 関数解析における計算可能性：有
界変動関数族における計算可能性、およびBanach空間の複素補間空間理論が計算可能性構造
と両立すること、などを示した。３ 型２マシンによる数学の計算可能性：型２マシンによ
る実数および諸空間の表現によって、線形部分空間の次元の計算方法、スペクトル定理の計
算可能版、などを示した。４ Grayコードによる計算：Grayコードへの埋めこみによる実数
の計算およびその応用としての位相空間の次元の計算可能性についての条件を提示した。
５ 計算可能性の論理構造：不連続関数は多くの場合Σ^0_1-排中律の各ケース内では通常
の計算アルゴリズムをもつことがわかる。それはまた極限再帰関数を使った計算としても表
される。この状況は存在記号の関数解釈によって基礎付けられるが、それはまた例による証
明検証とも関係があることがわかった。６ 現象としての計算可能性：消費者理論における
ネットワーク体系へのセラ・オートマタの応用、結び目理論におけるVssiliev不変量を共有
する簡単な異なる結び目の構成などが実現した。
萌芽的研究
人の知的活動において限定合理性のかかわる状況としていくつかのテーマをとりあげ、そ
れらについて証明論とセラ・オートマタの応用による考察を行った。
第一に二人のプレーヤによる帽子の色あてパズルを様相論理KD4で形式化し、プレーヤ
がパズルを解く過程の分析を行った。第二のプレーヤが正解に到達するために十分な体系
がKD4である。そこでは証明の正規化（カット除去）が可能である。第１のプレーヤの
「手持ちの情報では色当てができない」、すなわち「白であることが分からない」、とい
う主張を、プレーヤが体系を外から観察して「白であること」の証明不可能性を認識す、
と解釈する。これが「体系からの脱出」と呼ぶものである。実際に「１の帽子が白であ」
が体系KD4で証明不可能であることは、正規化の応用として示すことができる。第２のプ
レーヤはこの主張を聞いて新しい知識として取りこむ。新知識が手持ちの知識と矛盾しな
いことも同様に体系からの脱出により認識することができる。
体系からの脱出、という表現は超限的に見えるが、このような状況では証明可能性・不
可能性は決定可能であり、したがってパズル解きの全体の枠組みが決定可能である、とい
う重要な事実も示すことができた。そのためのプログラムを組むことは容易である。
第二にチープ・トーク・ゲームを定式化し、その計算機実験を行った。同じ学習アルゴ
リズムに基づくチープ・トークが、ゲームでの協力を容易にする場合と困難にする場合の
あることを確認し、それと被験者実験の結果を比較している。ゲームについてのチープ・
トークとゲームのなかでのチープ・トークの区別の難易と 協力の難易が対応していると
思われるので、今後その理論的解析を進める予定であ る。
