Logic and Computability

该奖项是根据2009年美国复苏和再投资法案（公法111-5）资助的。建议的研究重点是研究按计算相对复杂度排序的集合和函数的结构。特别强调将放在可定义性和自同构的问题上。这一领域还包括分析计算函数的难度与其他问题之间的关系，如增长率、它们在算术中定义的复杂性以及证明它们存在所需的公理系统的强度（反向数学）。反向数学的重点是分析基本的组合、模型论和集合论原理，这些原理似乎超出了标准理论的研究范围。此外，将发展一种基于可计算性理论概念的数学结构复杂性分类问题的新方法。这种方法应该允许应用程序处理当前方法无法处理的可数和高阶结构，或者（如在实数分析的情况下）只能通过编码到可数结构中来处理。该项目包括研究范围广泛的不可计算性理论和逻辑，包括理论和应用于数学和计算机科学的其他领域。在基础层面上，这项工作将阐明计算相对复杂性的本质，证明标准数学定理所需的公理的强度以及这些领域之间的关系。实际上，这个领域（可计算数学和模型理论以及逆向数学）的结果有时表明，对于某些重要任务没有算法，或者编写程序计算所需的结果需要比预期更多的信息。与自动机理论和自动结构相关的工作是基于资源非常有限的计算模型，这通常与实际计算问题相关。对其基本关系和函数可由自动机计算的结构进行理论和基础分析，最终也应具有实际意义。在大多数应用领域的主要焦点将是混合（连续和离散）控制理论的逻辑和数学基础，以及基于正在进行的理论工作的这些主题的算法的实际实现。这里的问题是理解如何在数学上对包括数字（离散）输入和逻辑约束以及模拟（连续）信息和约束的系统建模。

This award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5).The research proposed centers on investigations of the structures of sets andfunctions ordered by relative complexity of computation. Particular emphasiswill be placed on issues of definability and automorphisms. Also included inthis area is the analysis of the relations between the difficulty of computingfunctions and other issues such as rates of growth, complexity of theirdefinitions in arithmetic and the strength of axiom systems needed to provetheir existence (reverse mathematics). The emphasis in reverse mathematicswill be on analyzing basic combinatorial, model theoretic and set-theoreticprinciples that seem to lie outside the scope of the standard theoriesstudied. In addition, a new approach to the issue of classifying thecomplexity of mathematical constructions based on computability theoreticnotions will be developed. This approach should allow applications touncountable and higher order structures that are either out of reach ofcurrent approaches or (as in the case of analysis on the real numbers) onlyhandled through coding into countable structures.The proposed project includes research into a broad range of topics incomputability theory and logic both theoretical and applied to other areas ofmathematics and computer science. At the foundational level, this work willilluminate the nature of relative complexity of computation, the strength ofaxioms needed to prove standard mathematical theorems and the relationsbetween these areas. In practical terms, results in this area (computablemathematics and model theory as well as reverse mathematics) at times indicatethat there are no algorithms for certain important tasks or that moreinformation than might have been expected is needed to write programscalculating the desired results. The work related to automata theory andautomatic structures is based on a very resource-limited model of computationthat is often relevant to practical computing problems. The theoretical andfoundational analysis of structures whose basic relations and functions arecomputable by such automata should also eventually be of practicalsignificance. The primary focus in the most applied areas to be investigatedwill be the logical and mathematical foundations of hybrid (continuous anddiscrete) control theory as well as the practical implementation of algorithmsfor these subjects based on the theoretical work being done. Here the issue isto understand how to mathematically model systems that include both digital(discrete) input and logical constraints as well as analog (continuous)information and constraints.