Mathematical Sciences: Computability in Mathematics

数学科学：数学中的可计算性

• 批准号: 9634565
• 负责人: Peter Cholak
• 金额: $ 6.45万
• 依托单位: University of Notre Dame
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1996
• 资助国家: 美国
• 起止时间: 1996-08-01 至 2000-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9634565&HistoricalAwards=false
• 关键词: Mathematical; Sciences; Computability; Mathematics

DMS-9634565 Peter A. Cholak Cholak's main interest is in the interaction between various mathematical structures and different measures of computability. One such important mathematical structure is that of the computably enumerable sets -- those sets which can be enumerated by a Turing machine, with the relation of set inclusion. Cholak's project aims at understanding the relationships between the definable sets, the various dynamic properties of these sets, and the automorphisms of this structure. For example, Cholak wishes to determine the complexity (in terms of the above measures) of the question whether two computably enumerable sets are in the same orbit. This could help one show that certain jump classes are invariant within this structure. Another part of the project is to explore whether every partition of pairs has a non-high homogeneous set. Such a result would improve our understanding of the proof-theoretic strength of Ramsey's Theorem for pairs and of Weak Konig's Lemma. Cholak works in computability theory, an area of mathematical logic. Cholak's main interest is in the interaction between various mathematical structures and different measures of computability. For example, the most generally used model of computability is that of the Turing machine -- more or less an ideal computer running without any memory or time bounds. Cholak's research concerns the sets which can be listed using a Turing machine, with the hope of further understanding the relationships between sets which can be defined by formulas. Additionally, his research concerns various dynamic properties of these sets -- how fast or slow their enumeration is, and their information content.

DMS-9634565 Peter A. Cholak Cholak 的主要兴趣是各种数学结构和不同可计算性度量之间的相互作用。 一个这样重要的数学结构是可计算可枚举集合的结构——这些集合可以通过图灵机通过集合包含关系来枚举。 Cholak 的项目旨在理解可定义集合之间的关系、这些集合的各种动态属性以及该结构的自同构。 例如，Cholak 希望确定两个可计算可枚举集是否处于同一轨道的问题的复杂性（根据上述度量）。 这可以帮助人们证明某些跳转类别在此结构中是不变的。 该项目的另一部分是探索对的每个分区是否都具有非高同质集。 这样的结果将提高我们对拉姆齐对定理和弱柯尼希引理的证明理论强度的理解。 乔拉克研究可计算性理论，这是数理逻辑的一个领域。 乔拉克的主要兴趣在于各种数学结构和不同可计算性度量之间的相互作用。 例如，最常用的可计算性模型是图灵机——或多或少是一台没有任何内存或时间限制运行的理想计算机。 Cholak的研究涉及可以使用图灵机列出的集合，希望进一步理解可以用公式定义的集合之间的关系。此外，他的研究还涉及这些集合的各种动态属性——它们的枚举速度有多快或多慢，以及它们的信息内容。