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.