Computational irreducibility is one consequence of the halting problem being undecidable. If the halting problem were decidable, there couldn't be any computationally irreducible algorithms.
Right, these things are all corollaries of one another.
I think he might be referring to Rice's Theorem, which to be fair is reducible to the halting problem