Recursion Theory and Its Applications

University Of Wisconsin-Madison, Madison WI

Investigators

Abstract

In the proposed project, Cai plans to study classical recursion theory with emphasis on some interesting long-standing questions. In addition, he hopes to introduce new ideas and concepts to enrich the field, as well as to investigate some recent new results for different approaches and potential improvements. Cai also aims to expand the scope to applications of recursion theory, in particular he will continue the study of the degrees of provability, where proof-theoretic results can be proved using recursion-theoretic methods such as diagonalization and the recursion theorem. Recursion theory is a field of logic addressing effective content of mathematical practices (e.g., which of the mathematical procedures can be performed by automated machines, or computers). It has classical applications explaining why some mathematical problems (e.g., Hilbert's Tenth Problem) are theoretically unsolvable. The proposed project aims to improve the understanding of recursion theory by investigating old and new open problems, as well as to expand it by building connections to other fields such as proof theory. The proposed project has potential applications explaining how certain arithmetical facts could be theoretically unprovable.