# Math 114C: General Course Outline

## Catalog Description

**114C. Computability Theory (Formerly numbered 114A)**. Lecture, three hours; discussion, one hour. Requisite: course 110A or 131A or Philosophy 135. Effectively calculable, Turing computable, and recursive functions; Church/Turing thesis. Normal form theorem; universal functions; unsolvability and undecidability results. Recursive and recursively enumerable sets; relative recursiveness, polynomial-time computability. Arithmetical hierarchy. P/NP or letter grading.

**General Information**. If a function can be precisely defined, does that mean we can write a computer program for it? Math 114C looks at Turing machines and other models for making the concept of effective computability into genuine mathematics. The unsolvability of the halting problem demonstrates the existence of purely theoretical barriers to computability. There are decidable sets, effectively enumerable sets, and others.

Computability theory originated in ground-breaking work by Alonzo Church, Stephen Kleene, Emil Post, Alan Turing, and others, beginning in 1936. The topic is relevant to pure mathematics, theoretical computer science, and the philosophy of mathematics.