Computability Theory, Facing Outwards

Cuny Queens College, Flushing NY

Investigators

Abstract

In this project, the PI Russell Miller will continue his work using computability theory to analyze the difficulty of problems in other areas of mathematics. These areas include field theory and commutative and differential algebra; manifolds, both topologically and analytically; uncountable structures and the possibility of presenting and studying them effectively; and Blum-Shub-Smale computability and degree theory for the real numbers. In field theory, Miller has already made substantial progress, both by asking and answering natural computable-model-theoretic questions about fields, and also by noticing general questions about fields which can be answered using computability theory. He has taken the lead in introducing computability techniques to researchers outside mathematical logic, and has often been able to interest such people in his questions and his methods. Fields also intersect with his interest in uncountable structures: indeed, uncountable fields fit very naturally into the framework of local computability, the approach developed by Miller for considering uncountable structures within the Turing model of computation. In another approach to uncountable objects, Calvert and Miller have developed a definition of real-computable manifold, using the Blum-Shub-Smale model of computation on the real numbers. They have found that for the study of the fundamental group, the BSS model actually melts away and the Turing model of computation is appropriate. However, for consideration of distances on manifolds, using geodesics or other ways of defining a metric, they expect that BSS computation or other notions of computation, such as those from computable analysis, will be essential. Traditional computability theory examines the capabilities of digital computers and the limits on the problems which can be solved using such computers. Since the pioneering work of Alan Turing, it has been known that many problems cannot be solved by any digital computer running any program whatsoever. Even these "noncomputable" problems can be ranked by difficulty, however: problem A is easier (or at least, no more difficult) than problem B if we can show how a hypothetical program solving B would allow us to solve A as well. Recently, the PI Russell Miller has made contributions to computable model theory, the branch of this field in which one studies noncomputable problems about specific mathematical structures involving the natural numbers and the rational numbers. Structures involving all real numbers are much larger and therefore trickier to consider, but Miller and many others have introduced various methods for addressing these structures as well. Some of these methods use digital computers, while others assume exact-precision arithmetic on the real numbers or other structures. By examining the limits of these different models of computation, we can understand better how much extra power is provided by exact precision, and which mathematical problems require such precision if they are to be solved.