Logic Seminar
Sherwood Hachtman
UIC
Infinite Time Turing Machines and Determinacy
Abstract: Infinite time Turing machines, introduced by Hamkins and Kidder, extend the usual notion of Turing computability by allowing the machine to proceed for an arbitrary ordinal number of steps. These machines may either halt or enter a loop at some countable ordinal stage; thus there are several feasible notions of "Turing jump" for infinite time Turing computability. I will discuss a recent result of Philip Welch illustrating an intimate connection between the jump operator identifying those computations which "eventually settle" (loop with fixed output), and $\Sigma^0_3$ determinacy.
Tuesday November 24, 2015 at 4:00 PM in SEO 427