Philosophy of Computability

(3 Credit Hours) · Undergraduate

We shall study the philosophy of computability, following various philosophical issues and debates through history to contemporary times. Turing’s seminal 1936 paper greatly clarified the meaning of computability, introducing Turing machines, the halting problem, universal computers, and the concept of computable real numbers. His resolution of the Entsheidungsproblem provided a simple computability-based proof of the Gödel incompleteness phenomenon, challenging Hilbert’s program. His ideas on oracle computation lead to the hierarchy of Turing degrees, and the hierarchy of computational complexity similarly grows out of the P vs NP problem. Kolmogorov complexity reveals inherent limitations of our ability to gauge computational difficulty. The latter part of the course will focus on the philosophy of artificial intelligence, from classical treatments of the Turing test to the astonishing contemporary developments in artificial intelligence, which we shall explore with various student experiments using the latest AI services.