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希望确定问题的复杂性（根据上述度量）是否在同一轨道中计算出的两个集合。 这可以帮助一个人表明某些跳跃类在此结构中是不变的。 该项目的另一部分是探索对的每个分区是否具有非高均匀套件。 这样的结果将提高我们对Ramsey定理对Pairs和Konig的诱饵的证明理论强度的理解。 Cholak在计算理论中工作，这是数学逻辑领域。 Cholak的主要兴趣是各种数学结构与不同的可计算措施之间的相互作用。 例如，最常用的可计算性模型是图灵机器的模型 - 或多或少是一个理想的计算机运行，没有任何内存或时间范围。 Cholak的研究涉及可以使用图灵机列出的集合，以期进一步了解可以通过公式定义的集合之间的关系。此外，他的研究涉及这些集合的各种动态特性 - 枚举的速度或减慢其信息内容。