Mathematical Sciences: The Structure of Relative Definability

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

The investigator plans several projects designed to illuminate the dynamic features of computations and the connections between notions of computability in varying environments. He envisions separate studies on the global theory of various degree structures; the extension of embeddings problem for the recursively enumerable degrees; the relativized formulation of Lerman's theorem on finite ideals in the Turing degrees; Kechris' notion of universal Borel equivalence relations; and abstract complexity theory. Prominent among the questions to be addressed by this project are a number that bear on theoretical computability. They lie 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 sometimes more relevant to actual computations, and various aspects of that will also be considered.