Sherwood Hachtman : Infinite Time Turing Machines and Determinacy

Posted by Kostyantyn Slutskyy , part of the Logic Seminar.

At

Nov. 24, 2015, 4 p.m.

In

SEO 427

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.