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.