Incompleteness and the universal algorithm
This is a talk in the Hofstra Mathematics Seminar on 2021 April 21.
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$ which can be made to output anything so long as you run it in the right model of arithmetic.
This talk is self-contained and does not assume any background in computability theory nor mathematical logic.
Alan Turing surrounded by a multiverse of models of arithmetic in full bloom
[Copyright: Flowers for Turing, released under the Creative Commons Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) license]