Computability Theory and Logic

点击翻译按钮获取中文摘要

In this project Soare will study computability theory, particularly relative computability (Turing reducibility) of one set from another. The first objective is to study computability on the computably enumerable sets, and to relate their algebraic structure to the degree of information they encode and to the speed with which they can be enumerated with respect to some measure of computational complexity. Here attention is focused on the computably enumerable sets because they are generated by an algorithm, and hence most easily approximated by a computable function. The second objective is to study the relationship of computability to other mathematical objects, for example to models of Peano arithmetic, and to algebraic structures, such as Boolean algebras, and models of special theories like totally transcendental ones. For algebraic structures, the general problem is to determine exactly what information can be coded into the isomorphism type of that structure. The fundamental aim is to deepen our understanding of computability and its relation to structures in mathematics and computer science. In the 1930's various definitions of computable function were proposed by Turing, Church, Kleene, Goedel, and others. They were soon proved equivalent and they (particularly Turing's model) contributed during the war to the development of high speed digital computers. These models can be restricted with respect to computing resources such as time and space and give rise to computational complexity, an important part of modern computer science. Computability and algorithms now permeate many aspects of our lives. Modern researchers in computability and complexity are heirs to the founders like Turing and Goedel in that they are trying to classify the computable content of modern mathematics.