PH345 Spring term 2015-2016, 15 CATS

Module tutor: Walter Dean (W dot H dot Dean at warwick dot ac dot uk) Logistics: Lecture: Monday 12:00-14:00 S0.19 Seminar: Monday 18:00-19:00 S0.18 Office hours: Monday 14:00-15:00 S2.70 Related Module: PH340 (Logic III: Incompleteness and undecidability)
Current announcements Revision class: 10 May 13:00-14:00 MS.B3.03. The first lecture will take place on 11 January 2016. Seminars will start on 18 January. The module syllabus is now available here. Readings are now available here. Revision guide	Problem sets

Description:

The purpose of this module is to provide an accessible introduction to theoretical computer science and related philosophical issues about computation. Among the questions we will address are the following: What is a model of computation? Is it possible to provide a mathematical definition of the intuitive notion of a function computable by an algorithm? Do there exist functions which are non-computable (even in principle)? What does it mean to say that one function is harder to compute than another? What is a complexity class and what is the significance of the P vs. NP problem? What is the relationship between computation and proof in mathematics?