Mathematical Sciences: Recursively Enumerable Degrees and Priority Arguments

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

In degree theory, one tries to determine whether natural classes of oracles with differing information content have different algebraic properties. Thus questions about decidability of fragments of elementary theories of degree structures are pursued, in order to determine which degrees are definable, and how complicated the definitions must be. Rigidity questions, or questions about automorphisms of the structures are pursued, with the aim that if a structure is rigid, then sets with different information content do, in fact, look different algebraically. Such questions are within the scope of this project. The major tool of proof in recursion theory is the priority argument. A general framework for priority arguments at all levels is being sought, in the hope that a better understanding of priority arguments will assist in finding applications of this powerful combinatorial technique to real world problems. Computing, as it is practiced today, is of an interactive nature. Rather than the model of twenty years ago, where the computer was presented with a program and ran until it obtained an answer, the programs of today pause frequently and ask for input before continuing. Thus the true model of computing, as it is practiced, is the Turing machine with an oracle.