CPSC 313 Introduction to Computability

CPSC 313 is the introductionary course to theoretical computer science. It introduces regular expressions, languages, Turing Machines, and the famous Halting Problem.

Anyone using a computational device uses regular expressions. A Google search for e.g. "cat white" is a request to list webpages containing the substring "cat" as well as the substring "white." A search in an email client for e.g. "ucalgary.ca" will list emails containing the domain name "ucalgary.ca." Such searches are given by regular expressions, and the first part of the course discusses the power and complexity of such expressions.

To capture programming languages like HTML, CSS, Java and C, we need iterations and recursions. Regular expressions can model iterations, but not recursion. When we add the possibility of modelling recursion, we get context-free languages. The second part of the course discusses the power and complexity of context-free languages, and how context-free languages are related to core principles in programming languages such as counting and well-nested structures.

The third part of the course discusses the very foundation of computer science. It introduces the Turing Machine as the ultimate computer that can simulate all other computational devices. The course concludes with the most remarkable theorem that there are computational problems that can never be solved by any computer. We humbly conclude there are questions we can ask but can never find an answer to, no matter how much time and energy we allocate.

Since the course uses logic and mathematical arguments, MATH 271/273 and PHIL 279/377 are prerequisites. Read more at the official CPSC 313 calendar entry. CPSC 313 is a prerequisite for CPSC 413.

http://www.cpsc.ucalgary.ca/~hoyer/