Professor Stephen Jackson invites you to attend the

Master's Defense of August Sangalli

WHEN: Thursday, June 22, 2023

4:00pm in GAB 461

"Turing Computability and the Structure of the Turing Degrees "

ABSTRACT:

In 1936, Alan Turing introduced the definition of the Turing machine which convincingly characterized the informal notion of an algorithm and provided a negative solution for the decision problem. However, in a short section of his 1939 doctoral dissertation with Alonzo Church, he introduced the notion of the oracle Turing machine, a Turing machine equipped with a "black box" which instantaneously provides solutions to a certain problem. This sparked the study of relative computability, the notion of reducing a particular problem to another, and motivated Emil Post's formulation of the degrees of unsolvability known as the Turing degrees. We introduce the fundamentals of Turing computability and investigate various structural properties of the Turing degrees. We also utilize forcing techniques and a coding theorem by Slaman and Woodin to show the first order theory of the Turing degrees is computably isomorphic to second-order arithmetic.

Cookies and coffee will be served in GAB 472 following this event.