Computability Theory Learning Seminar

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

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

This is part II 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 Deveau's Theorem 4.2. Relevant computability theory concepts, including the recursion theorem, will also be introduced. We will consider a function F which, given the index for a computable group E := A ⊕ G = B ⊕ H, the indices for computable relations determining A, B, G, and H and the generators a and b of the cyclic groups A and B, outputs an index for a computable isomorphism between G and H. We will follow Deveau's proof and show that such a function F cannot be computable. This motivates our discussion of Turing degrees and the question of whether Fand the halting set are Turing equivalent in later talks.

MC 5417