This is a talk in the SHSU Mathematics and Statistics Department Colloquium on 2023 February 6.

[slides]

Work by mathematical logicians in the twentieth century established that the behavior of Turing machines—mathematical idealizations of computer programs—can be subject to undecidability. This undecidability can be understood from several different perspectives. Computability theoretically, there could be no general way to compute whether a Turing machine behaves a certain way. Proof theoretically, it could be that we can’t prove one way or another how a Turing machine behaves. Model theoretically, it could be that the behavior of a Turing machine depends on the world of mathematics in which it is ran. In 2011, W. Hugh Woodin discovered a striking case of the undecidability of how Turing machines behave. He produced a universal algorithm, a Turing machine whose output can be made to be anything by running it in the right world.

In this talk I will talk about the undecidability behavior of Turing machines and the universal algorithm. I will discuss how similar behavior can be seen higher up in the world of infinitary mathematics, via what in joint work with Joel David Hamkins we called the universal finite sequence. Both of these universal objects enable an application of modal logic—an extension of ordinary logic originally developed by philosophers—to mathematics, in a project called potentialism.