Computable Structure Theory

奈特从事可计算性理论的研究，这是数理逻辑的一个分支。有一系列的工作设计了计算某些函数的程序，还有为其他函数设计有用的近似程序的工作。有许多现实世界的功能(涉及人口、收入、对象在空间中的位置或事件在时间上的位置等)。只有通过近似值我们才能知道。奈特对数字系统和其他代数结构中的可计算性和可计算逼近特别感兴趣。传统上，可计算性理论处理的是可数对象。然而，重要的代数结构，如实数域，是不可数的。奈特感兴趣的一些问题涉及不可数结构的可计算性。奈特与凯伦·兰格和里德·所罗门一起，试图衡量在广义幂级数域中寻找多项式根的过程的复杂性。其中一些想法可以追溯到牛顿。奈特对乌里·安德鲁斯感兴趣的问题是，从模型理论的观点来看，表现良好的初级一阶理论何时具有可计算的模型。安德鲁斯和奈特得到了“强极小”理论的一个结果，条件是理论的碎片的复杂性保证了所有可数模型都有可计算的副本。在某些情况下，模型是由“工人”结构产生的，涉及嵌套近似。奈特对将可计算性技术应用于不可数结构很感兴趣。有不同的方法。其中一些涉及改变什么是可计算的定义。Noah Schweber定义了一个简约性，它允许我们使用标准的可计算性概念来比较任意基数结构的计算能力。这个奖项反映了NSF的法定使命，通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Knight works in computability theory, a branch of mathematical logic. There is a body of work designing procedures for computing certain functions, and there is work designing useful approximation procedures for other functions. There are many real-world functions (involving population, revenue, location of objects in space or events in time, etc.) that we can know only through approximations. Knight is particularly interested in computability and computable approximation in number systems and other algebraic structures. Traditionally, computability theory has dealt with countable objects. However, important algebraic structures such as the field of real numbers are uncountable. Some of the problems that interest Knight involve computability in uncountable structures. With Karen Lange and Reed Solomon, Knight is trying to measure the complexity of the process of finding roots of polynomials in fields of generalized power series. Some of the ideas go back to Newton. With Uri Andrews, Knight is interested in the problem of when an elementary first order theory that is well-behaved from the point of view of model theory has a computable model. Andrews and Knight have a result for "strongly minimal" theories, with conditions on the complexity of fragments of the theory guaranteeing that the countable models all have computable copies. For some cases, the models are produced by "workers" constructions, involving nested approximations. Knight is interested in applying the techniques of computability to uncountable structures. There are different approaches. Some involve changing the definition of what is computable. Noah Schweber defined a reducibility that allows us to compare the computing power of structures of arbitrary cardinality, using the standard computability notions. The idea is to collapse cardinals so that the structures being compared become countable.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.