Mathematical Sciences: Bounded Computation

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

Haught will continue her investigation of the degree structures induced by strengthenings of Turing computability. These strengthenings are obtained by placing size restrictions on various aspects of a Turing calculation. In particular, she is interested in truth table reducibility, weak truth table reducibility, and polynomial-time bounded Turing reducibility. She plans to develop technical methods for solving structural questions about the degrees, and to analyze the degree structures in terms of the proof techniques which are appropriate to the structures. In this way she hopes to uncover heretofore hidden connections among the various degree structures. Other aspects of the project are a continuation of Haught's study of the interactions between model theory and recursion theory in the setting of reverse mathematics, and an investigation of the properties of introreducible sets, but the major effort will be invested in understanding what it means for a proposition to be unprovable, making use of the various idealizations of computability cited above.