Kurt Gödel Research Center

2015 seminar talk: Flexible Turing Machines

Talk held by Ali Enayat (University of Gothenburg, Sweden) at the KGRC seminar on 2015-05-07.

Abstract

Suppose T is a consistent 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.

Recently Woodin (2011) 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 compare and contrast the aforementioned constructions of Kripke and Woodin, and will also present a refinement of Woodin's theorem, obtained in my collaborative work with Albert Visser, Volodya Shavrukov, and Rasmus Blanck.