Recursion theory has the halting problem. From it, you obtain the first example of an interesting Turing degree, and generalizing it, you get the Turing jump operator. 

The halting problem also plays an important role in (the boundary of) computational complexity theory, since it's one of the main tools for demonstrating the insolubility of computational problems.