The halting problem is algorithmically unsolvable:
Suppose there is an algorithm that solves it. Construct a Turing machine that behaves differently from every Turing machine. Then it behaves differently from itself, contradiction.
Gödel's incompleteness theorem:
Suppose a consistent and complete formal system is strong enough to express elementary mathematics. Then it can express the statement that a given Turing machine halts on a given input. By enumerating all proofs, we can solve the halting problem, contradiction.
The synopsis for the incompleteness theorem is is a little bit of cheating. The technically hard part of Gödel's proof is to show that a particular version of Peano arithmetic is strong enough to make the argument work (he had to do this since Turing machines weren't yet invented). But if he hadn't been able to pull this off, he would just have invented a slightly stronger system. The philosophically relevant part of the theorem is contained in this synopsis.
