Elan Roth, University of Pennsylvania
Formalizing Turing Reductions in Lean
Turing Reducibility and Turing Degrees simply characterize how difficult problems in mathematics are. We will begin by reviewing reductions and degrees, situating the degree structure as a partial order with a central spine of relativized halting problems. Then, we will explore Lean as a functional programming language and theorem prover looking at its capabilities and applications to modern mathematics. Finally, we will turn to the formal development of Turing reducibility, equivalence, and the induced degrees defined as a quotient. The goal is to demonstrate both how classical computability theory can be mechanized in Lean and how the resulting framework supports further formalization in logic and computable structure theory.
MC 5403