Mathematical Sciences: Computability in 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.