Computability and Computational Explanation

This Element is an introduction to classical computability theory and scientific efforts to use computability-theoretic notions to explain empirical phenomena. It is written for advanced undergraduates and graduate students in philosophy, assuming no prior exposure to computability theory. Its goals are threefold: (1) to introduce some important theoretical tools and results from classical computability theory; (2) to survey some of the ways these have been used to support explanatory projects in computer and cognitive science; and (3) to outline a few of the more prominent philosophical debates surrounding these projects.