Mathematical Sciences: Aspects of Computability

数学科学：可计算性方面

• 批准号: 8902437
• 负责人: Theodore Slaman
• 金额: $ 8.25万
• 依托单位: University of Chicago
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1989
• 资助国家: 美国
• 起止时间: 1989-07-01 至 1992-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8902437&HistoricalAwards=false
• 关键词: Mathematical; Sciences; Aspects; Computability

Slaman is engaged in several projects designed to illuminate the dynamic feature of computation, the structure of computable sets and the connection between notions of computability in varying environments. He plans separate studies in fragments of arithmetic; Turing degrees, global and local questions; recursion in higher types; and complexity theory. Investigations of this nature concern an idealized form of computing unlimited by memory size or practical time constraints. Positive results in this context may not be practically meaningful, but negative results, of course, are still perfectly meaningful. They constitute impossibility proofs in the very strong sense that even unreasonably huge memory and unreasonably lengthy computation runs will not suffice.

Slaman 参与了多个项目，旨在阐明计算的动态特征、可计算集的结构以及不同环境中可计算性概念之间的联系。 他计划单独研究算术片段；图灵度、全球和局部问题；更高类型的递归；和复杂性理论。 这种性质的研究涉及不受内存大小或实际时间限制的理想化计算形式。 在这种情况下，积极的结果可能没有实际意义，但消极的结果当然仍然非常有意义。 它们在非常强的意义上构成了不可能性证明，即使不合理的巨大内存和不合理的冗长的计算运行也不够。