MATH 29 Introduction to Computability

What does it mean for a function to be computable? This course examines several different mathematical formalizations of the notion of computability, inspired by widely varying viewpoints, and establishes the surprising result that all these formalizations are equivalent. It goes on to demonstrate the existence of noncomputable sets and functions, and to make connections to undecidable problems in other areas of mathematics. The course concludes with an introduction to relative computability. This is a good companion course to COSC 39; the two share only the introduction of Turing machines. Offered in alternate years.

Instructor

Miller

Prerequisite

None, but the student must be willing to learn to work abstractly and to read and write proofs.

Degree Requirement Attributes

QDS

The Timetable of Class Meetings contains the most up-to-date information about a course. It includes not only the meeting time and instructor, but also its official distributive and/or world culture designation. This information supersedes any information you may see elsewhere, to include what may appear in this ORC/Catalog or on a department/program website. Note that course attributes may change term to term therefore those in effect are those (only) during the term in which you enroll in the course.