Abstract:

Suppose T is a consistent r.e. (recursively enumerable) extension of Q (Robinson Arithmetic). A Turing Machine (hereafter TM) with program e is said to be T-flexible if for any prescribed natural number m, the theory T plus“on input 0, the output of the TM with program e is precisely the singleton {m}”is consistent. T-flexible TMs were first constructed by Kripke (1961). Note that here e is a concrete (standard) program. In 2011 Woodin introduced a new type of T-flexible TM for consistent r.e. extensions of PA (Peano arithmetic) such that: (1) T proves“on input 0, the output of the TM with program e is finite”, and (2) for every countable model M of T, and any M-finite set s extending the M-output of the TM with program e (when the input is 0), there is an end extension N of M satisfying T plus“on input 0, the output of the TM with program e is precisely s”.In this talk,I will (a) compare and contrast the aforementioned constructions of Kripke and Woodin, and (b) present a refinement of Woodin's theorem obtained in collaboration with Rasmus Blanck.