Mathematics 29 - Introduction to Computability

Institution:

Dartmouth College

Subject:

Description:

09S: 11 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 Computer Science 39; the two share only the introduction of Turing machines. Offered in alternate years. Prerequisite: None, but the student must be willing to learn to work abstractly and to read and write proofs. Dist: QDS. Weber.

Credits:

3.00

Credit Hours:

Prerequisites:

Corequisites:

Exclusions:

Level:

Instructional Type:

Lecture

Notes:

Additional Information:

Historical Version(s):

Institution Website:

www.dartmouth.edu

Phone Number:

(603) 646-1110

Regional Accreditation:

New England Association of Schools and Colleges

Calendar System:

Quarter

The Course Profile information is provided and updated by third parties including the respective institutions. While the institutions are able to update their information at any time, the information is not independently validated, and no party associated with this website can accept responsibility for its accuracy.