Computability Theory

Math 117b: Computability Theory

Winter 2023

Class Info

Class times: Tu/Th 1:00pm - 2:25pm
Class location: 387 Linde
Office: 204 Kellogg
Office Hours: Tu/Th 2:30 - 4:00pm

Course Description

Prerequisites: Ma 5 or equivalent, or instructor's permission. Welcome to Math 117!

This is a three term course providing an introduction to the basic concepts and results of the mathematical theory of computability and computational complexity theory. It requires no essential prerequisites, except perhaps some familiarity with abstract mathematical reasoning, at the level of a course like Math 5.

The Fall term will be first devoted to the discussion of various theoretical models of computation, like Turing machines, register machines, Markov algorithms, and recursive functions. We will demonstrate their equivalence and discuss Church's Thesis. Then we will study the basic theory of computable functions and effectively enumerable sets on the integers. We will use this theory to show that certain problems, like the so-called Halting Problem for Turing machines, are undecidable, i.e., cannot be solved algorithmically.

In the Winter term, we will discuss computability in the broader setting of mathematics. Some of the highlights here are a development of the Godel Incompleteness Theorems, the Boone-Novikov theorem on the undecidability of the word problem for groups, and the basics of the theory of algorithmic randomness. We will also discuss many examples of undecidable problems from logic, number theory, group theory, combinatorics, and computer science. No prior knowledge of any of these subjects is assumed. We will develop all the necessary background.

In the Spring term, we will start with a discussion of decidable problems, i.e., problems for which there are actually algorithms for their solution. Then we will introduce the basic concepts of the theory of computational complexity of algorithms. We will study the concept of feasible (polynomial time) computation and the relationship between deterministic polynomial (P) and nondeterministic polynomial (NP) computations, including NP-complete problems and the famous "P = NP" problem. We will also discuss probabilistic algorithms and derandomization.

Textbook

I will be posting my lecture notes on Canvas regularly, and there is no required textbook for the course.

Assessment

Your grade will be based on homework assignments. You are encouraged to collaborate on the homeworks, but you should write up solutions on your own. You are not allowed to copy homework solutions from any source, e.g. textbooks, online sources, or posted solutions from a previous iteration of Math 117.