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.