The most famous problems solved using recursion theory include the Entscheidungsproblem solved by Alan Turing, proving it impossible to algorithmically decide whether a statement is provable in a given axiomatic system, and the Halting Problem, demonstrating that there's no universal algorithm to decide if any given program halts.