The universal algorithm and the universal finite set, Prague 2018

This will be a talk at the Prague Gathering of Logicians & Beauty of Logic 2018, January 25-27, 2018.

Abstract. The universal algorithm is a Turing machine program $e$ that can in principle enumerate any finite sequence of numbers, if run in the right model of PA, and furthermore, can always enumerate any desired extension of that sequence in a suitable end-extension of that model. The universal finite set is a $\Sigma_2$ definition that can in principle define any finite set, in the right model of set theory, and can always define any desired finite extension of that set in a suitable top-extension of that model. I shall give an account of both results and describe applications to the model theory of arithmetic and set theory.

Leave a Reply