Computable Structure Theory

University Of Notre Dame, Notre Dame IN

Investigators

Abstract

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.