Skip to main content

Philosophy of Computation (PH345)

This module will provide an accessible introduction to theoretical computer science and related philosophical questions about computation.

We will start out by exploring a simple model of computation originally introduced by Alan Turing in 1936 -- i.e. what is now called a Turing machine. We will explore the power of this model using a computer simulator. his will lead us to ask questions such as the following: What is a universal computer? Can we construct one as a Turing machine? Do there exist mathematical functions which cannot be computed by a mechanical device (even "in principle")? What is Turing's Halting Problem and how is it related to the prior question? What does it mean to say that one function is more difficult to compute than another? What are the complexity classes P and NP? What is the significance of the P vs NP problem in complexity theory and how is it related to practical problems about subjects like deductive reasoning, cryptography, navigation, and social choice?

Philosophy of Computation
Timing and CATS

This module will run in the Spring Term and is worth 15 CATS.

Module Director:

Walter Dean