Computability Theory Learning Seminar

Thursday, November 24, 2022 10:30 am - 10:30 am EST

Xinyue (Cynthia) Xie & Layth Al-Hellawi, Department of Pure Mathematics, University of Waterloo

"Effectiveness properties of the Walker's Cancellation Theorem - Part III"

This is part III of a series of 4 talks in which we present and build upon the work in Deveau's PhD thesis and examine Walker's Cancellation Theorem from a computability theory perspective. In this talk, we will present a stronger version of Deveau's Theorem 4.1. Deveau's Theorem 4.1 states that given groups E:= A ⊕ G = B ⊕ H, where A ≅ B are cyclic with known generators, G and H are always computably isomorphic with some isomorphism f. Furthermore, if A and B are known to be finite, then f can be constructed uniformly in the indices of the groups. We will prove that regardless of the cardinality of A and B, the function that computes f is Turing reducible to the halting set. The notions of Turing reducibility, Turing degree and the Turing jump operator will be introduced.

MC 5417