Computability and Complexity in Constructive Mathematics

构造数学中的可计算性和复杂性

• 批准号: 15500005
• 负责人: ISHIHARA Hajime
• 金额: $ 2.3万
• 依托单位: Japan Advanced Institute of Science and Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2003
• 资助国家: 日本
• 起止时间: 2003 至 2006
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-15500005/
• 关键词: Constructive Mathematics; Computability; Computational Complexity; Reverse Mathematics; 国際研究者交流; ドイツ:アメリカ:ニュージー

From 2003 to 2006, for 4 years, we have done a research on computability and complexity in constructive mathematics. During the research, we have got some important and better understandings on the subject. One of the most important understanding is that computability and complexity in constructive mathematics can be dealt with better within a more general framework of constructive reverse mathematics. Moreover, progress in constructive mathematics, such as constructive set theory and topology in constructive mathematics, has produced new problems in computability and complexity in constructive mathematics, and in constructive reverse mathematics.In this research project, we have proposed a new framework of constructive reverse mathematics. We have investigated relationship between Brouwer's fan theorem and weak Koenig's lemma, with Dr. Josef Berger, and computability in these theorems. With Professor Peter Aczel, Dr. Laura Crosilla, Professor Erik Palmgren, and Associate Professor Peter Schuster, we have dealt with a problem of constructive reverse mathematics in the constructive Zermelo-Fraenkel set theory. Concerning topology in constructive mathematics, we have worked on constructions of quotient topologies in constructive set theory and type theory, with Professor Erik Palmgren, and on quasi-apartness and neighbourhood spaces, with Professor Ray Mines, Associate Professor Peter Schuster and Dr. Luminita Vita. Furthermore, we have treated computational complexity in constructive theory of real numbers and the constructive intermediate value theorem, and a constructive version of Banach's inverse mapping theorem in F-spaces as an application of Baire's theorem.Further research project is putting research in constructive reverse mathematics forward with progress in constructive mathematics such as constructive set theory and constructive topology.

从2003年到2006年，在4年中，我们对建设性数学的计算性和复杂性进行了研究。在研究期间，我们对该主题有一些重要，更好的理解。最重要的理解之一是，在建设性反向数学的更一般框架内，可以更好地处理建设性数学的可计算性和复杂性。此外，建设性数学的进展，例如建设性数学的建设性集合理论和拓扑，在建设性数学的计算和复杂性以及建设性的反向数学方面产生了新的问题。在这项研究项目中，我们提出了一个新的建设性反向数学的框架。我们已经调查了Brouwer的Fan定理与Josef Berger博士的弱Koenig的引理与这些定理中的可计算性之间的关系。在彼得·阿克塞尔（Peter Aczel）教授，劳拉·克罗西拉（Laura Crosilla）博士，埃里克·帕尔普伦（Erik Palmgren）教授和副教授彼得·舒斯特（Peter Schuster）中，我们在建设性的zermelo-fraenkel set理论中处理了一个建设性反向数学的问题。关于建设性数学的拓扑，我们与Erik Palmgren教授以及准校园和邻里空间一起研究了商集理论和类型理论中商的构造，与Ray Mines，副教授Peter教授Peter教授和Luminita Vita博士一起工作。此外，我们在实数和建设性的中间值定理中将计算复杂性处理为BANACH在F空间中的逆映射定理的建设性版本作为Baire的定理的应用。FurtherResearch项目在建设性的逆向数学方面将研究在建设性数学中促进了建设性的数学发展，例如建设性的构建性设置理论和构建性的专业化学。

项目成果

Quasi-apartness and neighbourhood spaces

准公寓和邻里空间

• 发表时间: 2006
• 期刊: Ann. Pure Appl. Logic 141
• 作者: Y.Yamaguchi;F.Takagi;K.Yamashita;H.Shimizu;H.Maeda;K.-I.Sotowa;K.Kusakabe;Y.Yamasaki;S.Morooka;T.Watanabe;Hajime Ishihara
• 通讯作者: Hajime Ishihara

Unique existence and computability in constructive reverse mathematics

构造性逆向数学中的独特存在性和可计算性

• 期刊: Lect. Notes Comput. Sci. (印刷中)
• 作者: A.Ito;K.Inoue;Y.Wang;Michiro Kondo;大木 憲二;Hajime Ishihara
• 通讯作者: Hajime Ishihara

A Piano Duo Support System for Parents to Lead Children to Practice Musical Performances

家长带领孩子练习钢琴二重奏支持系统

• 发表时间: 2007
• 期刊: ACM Transactions on Multimedia Computing, Communications and Applications (ACM TOMCCAP) Vol.3, No.2
• 作者: Chika Oshima;Kazushi Nishimoto;Norihiro Hagita
• 通讯作者: Norihiro Hagita

Binary refinement implies discrete exponentiation

二进制细化意味着离散求幂

• 发表时间: 2006
• 期刊: Studia Logica 84
• 作者: 櫻井;草刈;西田;酒井;坂部;Peter Aczel
• 通讯作者: Peter Aczel

A Tangible Composition System for Promoting Children to Create Music by Reflectively Manipulating Notes

促进儿童通过反思性操作音符创作音乐的有形作曲系统

• 发表时间: 2005
• 期刊: Journal of Japan Society for Fuzzy Theory and Intelligent Informatics Vol.17, No.2
• 作者: Mao Makino;Chika Oshima;Rodney Berry;Naoto Hikawa;Kazushi Nishimoto;Masami Suzuki;Norihiro Hagita
• 通讯作者: Norihiro Hagita