Collaboration in Computability

可计算性协作

• 批准号: 1600625
• 负责人: Julia Knight
• 金额: $ 10万
• 依托单位: University of Notre Dame
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-05-01 至 2022-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1600625&HistoricalAwards=false
• 关键词: Collaboration; Computability

This award will support activities of a research network of mathematicians working in computability theory. This project will facilitate collaborative work of faculty and graduate students from the U.S., Russia, Kazakhstan and Bulgaria. The research is in quickly developing areas of computability, and this project has two broad goals: the first goal is more rapid scientific progress resulting from a network of collaborators, from all four countries, enabling them to pool their ideas to solve fundamental problems. The second goal is to provide opportunities for students and young researchers to participate actively in the world community of scientists.Computability as a research area has blossomed in recent years, with many exciting new results that involve combining techniques from pure computability with sophisticated algebra, model theory, set theory, and/or probability. There are also stronger ties with computer science. The proposal named 20 senior participants, and students and postdocs will also participate in the activities supported by the grant. The proposed work includes a variety of problems. There are problems on the difficulty in building a copy of a structure (degree spectra), and on the relative computing power of structures (Muchnik reducibility). There are problems on the internal complexity of structures (Scott rank) and on the difficulty of describing a structure, measured by the complexity of a ``Scott sentence''. In particular, there are problems on Scott sentences for groups. Some problems concern uncountable structures such as the ordered field of reals. There are problems on ``jumps'' of structures and a strong notion of ``jump inversion''. There are problems on complexity of isomorphisms, and on automorphisms, in particular, for vector spaces. There are problems on degree structures (enumeration degrees, and ``continuous'' degrees). There are problems on ``numberings''. At least two problems, one on the ``Hanf number'' for Scott sentences of computable structures, and one on the relative computing power of the ordered field of reals and an expansion by an arbitrary continuous function, have been solved since the proposal was submitted.

该奖项将支持从事可计算理论的数学家研究网络的活动。该项目将促进来自美国、俄罗斯、哈萨克斯坦和保加利亚的教师和研究生的合作工作。这项研究是在快速发展的可计算领域进行的，该项目有两个广泛的目标：第一个目标是由来自所有四个国家的合作者组成的网络带来更快的科学进步，使他们能够汇集他们的想法来解决基本问题。第二个目标是为学生和年轻研究人员提供积极参与世界科学家社区的机会。近年来，可计算性作为一个研究领域蓬勃发展，许多令人兴奋的新结果涉及将纯可计算性与复杂代数、模型论、集合论和/或概率论相结合的技术。与计算机科学的联系也更紧密。该提案提名了20名高级参与者，学生和博士后也将参与该基金支持的活动。提议的工作包括各种各样的问题。在构造结构副本的难度（度谱）和结构的相对计算能力（Muchnik可约性）上存在问题。在结构的内部复杂性（斯科特等级）和用“斯科特句”的复杂性来衡量描述结构的难度上存在问题。特别是群体的斯科特句存在问题。一些问题涉及不可数结构，如实数的有序域。在结构的“跳跃”和“跳跃反转”概念上存在问题。关于同构的复杂性问题，特别是关于向量空间的自同构的复杂性问题。在学位结构（枚举学位和“连续”学位）上存在问题。“编号”有问题。自该方案提出以来，至少解决了两个问题，一个是关于可计算结构Scott句的“汉夫数”问题，另一个是关于实数有序域的相对计算能力和任意连续函数的展开问题。

项目成果

Interpreting a field in its Heisenberg group

解释海森堡群中的域

• DOI: 10.1017/jsl.2021.107
• 发表时间: 2022
• 期刊: The Journal of Symbolic Logic
• 作者: Alvir, R.;Calvert, W.;Goodman, G.;Harizanov, V.;Knight, J.;Morozov, A.;Miller, R.;Soskova, A.;Weisshaar, R.
• 通讯作者: Weisshaar, R.