Computability Theory, Facing Outwards

点击翻译按钮获取中文摘要

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, commutative and differential algebra, model theory, and number theory, as well as the possibility of describing uncountable structures and studying them effectively. 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. Indeed, in certain cases we can learn whether a particular problem is computable or not by determining where related noncomputable problems sit in this hierarchy. Recently, the PI has made contributions ranging from solutions to concrete problems about deciding whether certain polynomial equations can be satisfied using rational numbers, to more abstract questions about the difficulty of solving algebraic differential equations and the relative difficulty of considering structures from different areas of mathematics.The PI recently collaborated with several number theorists to produce new evidence for the undecidability of Hilbert's Tenth Problem for the rational numbers, the problem which asks for an algorithm to decide which Diophantine equations have rational solutions. He plans to continue this work, considering the specific question of subrings of the rationals of density 0 (i.e., "very close" to the integers). In field theory, he has made substantial progress, both by asking and answering natural computable-model-theoretic questions about the difficulty of computing isomorphisms between fields, and also by using computability theory to answer general questions about the complexity of fields in relation to the complexity of other mathematical structures. He hopes to address a key question in differential algebra, whose solution would help mathematicians better understand differentially closed fields and solutions to differential equations. (These are analogous to algebraically closed fields, but are much less well understood at present.) For some years now he has taken the lead in introducing computability techniques to researchers throughout mathematics, and has often been able to interest such people in his questions and his methods. With this grant, those efforts will most certainly continue.