Computability and Complexity in Mathematics

数学中的可计算性和复杂性

• 批准号: 1363310
• 负责人: Antonio Montalban
• 金额: $ 20万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-07-15 至 2017-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1363310&HistoricalAwards=false
• 关键词: Computability; Complexity; Mathematics

Antonio Montalban will study problems in Computability Theory. He is interested in the interplay between complexity and mathematics. In mathematics, as we all know, some structures are more complicated than others, some constructions more complicated than others, and some proofs more complicated than others. He plans to apply methods from computability theory to study the complexity of various areas of both classical mathematics and foundations of mathematics.One of our objectives is to study of the computational properties of counterexamples to Vaught's conjecture, which is one of the most well-known and longest-standing conjectures in logic. This is with an eye towards either showing that those counterexamples do not exist, or just trying to understand them if they do exist. Montalban has already shown that being a counterexample to Vaught's conjecture is equivalent to a couple of purely computability-theoretic properties, and he has in mind a few other properties that might also end up being equivalent.

Antonio Montalban将研究可计算性理论中的问题。他对复杂性和数学之间的相互作用感兴趣。在数学中，我们都知道，有些结构比其他结构更复杂，有些构造比其他构造更复杂，有些证明比其他证明更复杂。他计划应用可计算性理论的方法来研究古典数学和数学基础的各个领域的复杂性。我们的目标之一是研究Vaught猜想的反例的计算性质，Vaught猜想是逻辑学中最著名和历史最悠久的猜想之一。这是着眼于要么表明这些反例不存在，或者只是试图理解他们，如果他们确实存在。Montalban已经证明了作为Vaught猜想的反例等价于两个纯可计算性理论性质，并且他还想到了其他一些可能最终等价的性质。