Neel Krishnaswami's answer here points to references connecting the above results under the umbrella of category theory: http://cstheory.stackexchange.com/questions/10635/halting-problem-uncomputable-sets-common-mathematical-proof/10636#10636