This is a talk in the Talk Math With Your Friends seminar on 2020 Sept 17.

[slides]

In 1936 Alan Turing introduced a mathematical model of computation. The Turing machine has since become the standard way to formalize the notion of computability. Many incompleteness results can be recast as statements about Turing machines. For example, Kurt Gödel’s second incompleteness theorem can be equivalently stated as saying that whether certain Turing Machines halt depends upon in which model of arithmetic they are ran. In this talk I will present a particularly striking instance of this phenomenon, Hugh Woodin’s universal algorithm. Woodin produced a single Turing machine $p$ so that no matter what password—finite sequence of natural numbers—you write down there is a model of arithmetic $M$ so that if you run $p$ in $M$ it will output exactly your password. Time permitting, I will discuss an application of Woodin’s universal algorithm to philosophy of mathematics, developed by Joel David Hamkins.

This talk is self-contained and does not assume any background in computability theory nor mathematical logic.