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.