Mathematical Sciences: Bounded Computation

数学科学：有界计算

• 批准号: 9002798
• 负责人: Christine Haught
• 金额: $ 3.35万
• 依托单位: Loyola University of Chicago
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1990
• 资助国家: 美国
• 起止时间: 1990-06-15 至 1992-11-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9002798&HistoricalAwards=false
• 关键词: 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.

豪特将继续她对图灵可计算性增强引起的学位结构的研究。这些加强是通过对图灵计算的各个方面施加大小限制来获得的。特别是，她对真值表的可约性、弱真值表的可约性和多项式时间有界的图灵可约性感兴趣。她计划开发解决学位结构问题的技术方法，并根据适用于学位结构的证明技术来分析学位结构。通过这种方式，她希望能发现各种程度结构之间迄今隐藏的联系。该项目的其他方面是霍特在逆数学背景下对模型理论和递归理论之间相互作用的研究的继续，以及对可约集合的性质的调查，但主要的努力将投入到理解命题是不可证明的意味着什么上，利用上面提到的各种可计算性理想化。