Logic and Computability

该研究提出了以计算的相对复杂性排序的集合和函数的结构的研究。将特别强调可定义性和自同构问题。这一领域还包括分析计算函数的难度与其他问题之间的关系，例如增长速度、它们在算术中定义的复杂性以及证明它们存在所需的公理系统的强度(逆数学)。逆数学的重点将放在分析基本的组合原理上，这些原理似乎超出了所研究的标准理论的范围。纯可计算性理论的方法将在模型理论和微分几何中使用的概念领域进行应用。可计算模型理论的重点将放在如何选择给定结构的不同表示法来影响结构元素上的各种关系或程序的计算复杂性。自动机理论，特别是处理可计算复杂性的自动结构的问题也将被讨论。建议的项目包括对可计算性理论(递归理论)和逻辑的广泛主题的研究，既有理论上的，也有应用于数学和计算机科学的其他领域的。在基础水平上，这项工作阐明了计算的相对复杂性的性质，证明标准数学定理所需的公理的强度，以及这些领域之间的关系。在实践中，这一领域的结果(可计算数学和模型理论以及逆数学)有时表明，对于某些重要任务没有算法，或者需要比预期更多的信息来编写计算期望结果的程序。与自动机理论和自动结构相关的工作是基于一个非常有限的计算模型，该模型通常与实际计算问题相关。对其基本关系和功能可由这种自动机计算的结构的理论和基础分析最终也应该具有实际意义。

The research proposed centers on investigations of the structures of sets and functions ordered by relative complexity of computation. Particular emphasis will be placed on issues of definability and automorphisms. Also included in this area is the analysis of the relations between the difficulty of computing functions and other issues such as rates of growth, complexity of their definitions in arithmetic and the strength of axiom systems needed to prove their existence (reverse mathematics). The emphasis in reverse mathematics will be on analyzing basic combinatorial principles that seem to lie outside the scope of the standard theories studied. Applications of the methods of pure computability theory will be made in the areas of model theory and notions used in differential geometry. The emphasis in computable model theory will be on the ways in which choosing different representations of a given structure affect the computational complexity of various relations or procedures on the elements of the structure. Issues in automata theory and especially automatic structures that deal with computable complexity will also be addressed.The proposed project includes research into a broad range of topics in computability theory (recursion theory) and logic both theoretical and applied to other areas of mathematics and computer science. At the foundational level, this work illuminates the nature of relative complexity of computation, the strength of axioms needed to prove standard mathematical theorems and the relations between these areas. In practical terms, results in this area (computable mathematics and model theory as well as reverse mathematics) at times indicate that there are no algorithms for certain important tasks or that more information than might have been expected is needed to write programs calculating the desired results. The work related to automata theory and automatic structures is based on a very limited model of computation that is often relevant to practical computing problems. The theoretical and foundational analysis of structures whose basic relations and functions are computable by such automata should also eventually be of practical significance.