Mathematical Sciences: Logic and Computability

该项目包括研究可计算性理论（递归理论）和应用于计算机科学各个领域的逻辑的广泛主题。第一个领域包括递归可枚举集的研究，从图灵到多项式时间的几种复杂程度的结构，以及一些数学定理的证明理论复杂性。第二个研究领域包括非单调逻辑源的分析和开发，并发编程模型，资源有界逻辑，以及线性规划思想和算法在数据结构和逻辑编程中的应用。该项目解决了理论可计算性问题和更实际的问题。理论上的是所谓的递归理论，它处理的是一个不受时间和空间限制的可计算性模型。虽然这些问题的答案有能力阐明实际问题，但只有当答案是否定的时候，它们才是真正实际的，因为即使在不限制可用资源的情况下，也不能计算某些东西，这确实是一个非常有力的说法。可计算性理论的精细结构甚至与实际计算更相关，并且还将考虑其各个方面。

This project includes research into a broad range of topics in computability theory (recursion theory) and into logic applied to various areas of computer science. Included in the first area are investigations of recursively enumerable sets, several structures of degrees of complexity from Turing to polynomial time, and the proof theoretic complexity of some mathematical theorems. The second area of research includes the analysis and development of a source in nonmonotonic logic, concurrent programming models, resource bounded logic, and applications of linear programming ideas and algorithms to data structures and logic programming. Both theoretical computability questions and more practical ones are addressed by this project. The theoretical ones are the ones in what is known as recursion theory, which deals with a model of computability knowing no bounds on time or space. Although answers to such questions have the ability to illuminate practical questions, they are really practical only when their answers are negative, for it is a very strong statement indeed to say that something cannot be computed even when one puts no limits on resources available for the purpose. The finer structure of computability theory is even more relevant to actual computations, and various aspects of that will also be considered.