The CIM Courses system will be down temporarily undergoing routine maintenance.

Catalog Pages referencing this course

Programs referencing this course

Columbian College of Arts and Sciences

Mathematics (MATH)

MATH

3730

Computability Theory

Computability Theory

3

Course Type

Lecture

Default Grading Method

Letter Grade

No

No

MATH 2971 or permission of instructor

Corequisites

Frequency of Offering

Term(s) Offered

Are there Course Equivalents?

No

No

Fee Type

No

The unlimited register machine as a model of an idealized computer. Computable and partial computable functions; Church–Turing thesis. Kleene’s recursion theorem. Algorithmic enumerability. Unsolvability of the halting problem and other theoretical limitations on what computers can do. Discussion of Goedel’s incompleteness theorem.

Uploaded a Course Syllabus

Course Attribute

CCAS - GCR: Q & L

Key: 5776