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 IV"

This is part IV 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. We will continue our investigation of the function F which, given the index for a computable group E:= A ⊕ G = B ⊕ H, where A ≅ B are cyclic and the indices for computable relations determining A, B, G and H, outputs an index for a computable isomorphism between G and H. From the previous talks, we know that regardless of whether the generators a and b of the groups A and B are given to F as inputs, we have ∅ <_T F ≤_T ∅'. In this final talk, we will focus on the open question of whether ∅' ≤_T F. That is, can we code the halting set into F? We will prove that ∅' ≤_T F when a and b are not known in advance and will present some attempts that we have made in the case where a and b are fixed. If time permits, we will also present some well-known theorems in computability theory, such as the Use Principle and the Jump Theorem.

MC 5417