PHIL 4420/MATH 4030 - Computability and Logic

Course Overview

This course covers basic concepts and results in mathematical logic and computability, including Turing Machines, Church’s Thesis, the halting problem and other limitations to computation, semi-decidability of first-order logic, and Godel’s incompleteness results. A more philosophical discussion on the implications of these results is included as well.

The only official prerequisite for this course is PHIL-2140 Introduction to Logic, but it certainly helps to have taken PHIL-4140 Intermediate Logic or CSCI-2400 Models of Computation as well.