Collaboration in Computability

该奖项将支持从事可计算性理论工作的数学家研究网络的活动。该项目将促进来自美国、俄罗斯、哈萨克斯坦和保加利亚的教师和研究生之间的合作。这项研究是在快速发展的可计算性领域进行的，该项目有两个广泛的目标：第一个目标是通过来自所有四个国家的合作者网络实现更快的科学进步，使他们能够汇集想法来解决根本问题。第二个目标是为学生和年轻的研究人员提供积极参与世界科学界的机会。可计算性作为一个研究领域近年来蓬勃发展，有许多令人兴奋的新结果，涉及将纯可计算性与复杂的代数、模型理论、集合论和/或概率论的技术相结合。与计算机科学也有更紧密的联系。该提案点名了20名资深参与者，学生和博士后也将参加由赠款支持的活动。拟议的工作包括各种问题。存在着构建结构副本的难度(度谱)和结构的相对计算能力(Muchnik可缩减性)的问题。在结构的内部复杂性(Scott等级)和描述结构的难度方面都存在问题，以“Scott语句”的复杂性来衡量。尤其是在针对群体的Scott语句上存在问题。一些问题涉及到不可数结构，如实数的序域。关于结构的“跳跃”和“跳跃反转”的强烈概念存在问题。存在同构的复杂性问题，特别是向量空间的自同构问题。在程度结构上存在问题(枚举度和“连续”度)。‘’编号‘’有问题。自提案提交以来，至少已经解决了两个问题，一个是关于可计算结构的Scott语句的“Hanf数”，一个是关于实数的有序域的相对计算能力和任意连续函数的展开。

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.