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的研究涉及可以使用图灵机列出的集合，希望进一步理解可以通过公式定义的集合之间的关系。此外，他的研究涉及这些集合的各种动态特性-它们的枚举速度有多快或多慢，以及它们的信息内容。