Are there mathematical limits to the kinds of problems we can solve computationally? Turing famously proved that there are, by showing that no computer can solve the halting problem. Similar results have now been discovered throughout computer science, in areas as diverse as computer security, computer graphics, and software engineering. In this project, I argue that these results furnish an underappreciated form of computational explanation, which I call limitative explanation. Roughly speaking, these explain limits on the powers of physical computing systems. This project aims to understand these results and their implications for our understanding of physical computation.
- Mathematical Explanation in Computer Science
- A paper arguing against mechanistic and interventionist conceptions of computational explanation (under review)
- A paper discussing the different explanatory virtues of extensionally equivalent computational models (in preparation)
Back to projects.