1st Semester 2013/14: Computational Complexity in Philosophy and Cognitive Science
- Instructors
- ECTS
- 6
- Description
- Computability theory (Church, Turing, Gödel and others) has significantly influenced philosophy, logic, artificial intelligence, and cognitive science. In the 1960's, with the growing availability of computers, it became increasingly clear that the real question might be not what is computable in general but rather what is efficiently or feasibly computable. This new perspective gave rise to the computational complexity theory with its spectacular discoveries (NP-completness, public-key cryptography, theoretical foundations of machine learning, quantum computing, etc). Surprisingly, computational complexity still has relatively little influence over other disciplines. In this course, we will survey some aspects of complexity theory that lead to new insights in philosophy, AI, and cognitive science. For instance, we will discuss how complexity theory can contribute to the strong AI debate (Turing test), cognitive science (Tractable Cognition thesis), the problem of logical omniscience, Hume's problem of induction, Goodman's grue riddle, economic bounded rationality, formal semantics, and the nature of mathematical knowledge.
- Organisation
- In the first lecture I will cover some of the background required for the course, regarding mostly computational complexity theory. Then the students will present (selected fragments) of papers overviewing the applications of computational complexity in philosophy, cognitive science, AI, and linguistics. The focus of the project will be on critical discussion of arguments, including both conceptual and mathematical aspects. The rest of the project period will be devoted to original research: deepening and extending the discussed applications of complexity theory, identifying and discussing aspects of the theory that could benefit from philosophical analysis, and vice versa, finding new philosophical and cognitive problems that could be studied from the computational complexity perspective.
- Prerequisites
- This is an interdisciplinary project combining philosophy, computer science, and cognitive science. The course will encourage collaboration between students with different backgrounds. Familiarity with the (basics of) computational complexity theory will be helpful.
- Assessment
- This course is worth 6 EC. Students will be graded on the basis of oral presentations and a short research report. Participation in class discussion will also be assessed.
- References
- The following papers are the starting point for this project:
- Scott Aaronson. "Why Philosophers and Cognitive Scientists Should Care About Computational Complexity", in "Computability: Goedel, Turing, Church, and beyond," MIT Press, 2012.
- Alistair Isaac, Jakub Szymanik, and Rineke Verbrugge. "Logic and Complexity in Cognitive Science", Johan van Benthem on Logical/Informational Dynamics, A. Baltag and S. Smets (eds.), Trends in Logic, Outstanding Contributions to Logic, Trends in Logic book series, Springer, 2014 (forthcoming).
- Iris van Rooij. "The Tractable Cognition Thesis", Cognitive Science, 2008, 32, 939-984.