Is one definition of the word paradox, "something that can be used to prove the halting problem undecidable?"
It sounds like you are looking for a characterisation of the features required to capture diagonalization arguments.  Lawvere's Diagonal Arguments and Cartesian Closed Categories unified each of the main diagonal arguments back in 1969, including Cantor's and Rice's Theorems, the halting problem, and Gödel's first incompleteness theorem.

Yanofsky's 2003 tutorial discussion A Universal Approach to Self-referential Paradoxes, Incompleteness and Fixed Points provides a nice overview of Lawvere's ideas  (arXiv:0305282).

More recently, Samson Abramsky and Jonathan Zvesper have been taking this further (arXiv:1006.0992).