This is a talk in the Analysis, Logic And Physics Seminar at Virginia Commonwealth University on 2020 October 30.
Kurt Gödel’s celebrated incompleteness theorems can be reformulated in computability theoretic terms: there are computer programs so that whether they halt and produce an output is independent of the axioms of arithmetic. Phrased differently, there are programs so that if ran in the natural numbers they produce no output, but if ran in certain nonstandard models of arithmetic then they do produce an output. In 2011, Hugh Woodin constructed a particularly striking instance of this incompleteness of computability phenomenon. Woodin produced a universal algorithm, a single program so that you can make it output whatever finite output you want by running it in the correct nonstandard universe. I will present on Woodin’s universal algorithm and an application of his ideas, developed by Joel David Hamkins, to the philosophy of mathematics. Time permitting, I will touch on recent work in generalizing Woodin’s universal algorithm to models of set theory.