MATH 684 - Recursion Theory
Section: 001
Term: WN 2018
Subject: Mathematics (MATH)
Department: LSA Mathematics
Page Index

Details

Credits:
3
Requirements & Distribution:
BS
MATH 681 or equivalent.
BS:
This course counts toward the 60 credits of math/science required for a Bachelor of Science degree.
Repeatability:
May not be repeated for credit.
Primary Instructor:

Description

This course is about two fundamental concepts of mathematics: computability and provability. The first topic to be covered is a precise definition of computability in principle, where "in principle" means that a computation must give a result after finitely many steps but we place no specific bounds on the number of steps or the amount of memory used. In fact, several precise definitions of computability have been proposed, but they all turn out to be equivalent. We shall discuss a few of them and develop the tools needed to prove their equivalence. We shall also discuss the connection between computability and definability, giving specific examples of definable but uncomputable functions.

The second part of the course, building on the concepts and techniques of the first part, explores the limits of provability in axiomatic systems. It includes the proof of Goedel's incompleteness theorems --- that reasonable axiomatic systems cannot exactly capture truth, even in the limited domain of the arithmetic of natural numbers, and that they cannot prove their own consistency.

The final part of the course is a deeper study of computability, and in particular a classification of uncomputable functions according to a criterion of the form "if we had access to values of f then we could compute values of g." The analysis of this relation has led to some deep andelegant arguments, the simplest of which will be covered in this course.

Text: Fundamentals of Mathematical Logic , Peter G. Hinman Optional

Course Requirements:

No data submitted

Intended Audience:

Prerequisites: It is useful to have had a first course in mathematical logic, but it is not strictly necessary if you are willing to take some basic facts on faith.

Class Format:

No data submitted

Schedule

MATH 684 - Recursion Theory
Schedule Listing
001 (LEC)
P
32185
Open
12

-
 TuTh 1:00PM - 2:30PM 1866 EH

Textbooks/Other Materials

NOTE: Data maintained by department in Wolverine Access. If no textbooks are listed below, check with the department.

ISBN: 9781568812625
Fundamentals of mathematical logic, Author: Peter G. Hinman., Publisher: A.K. Peters 2005
Optional

Syllabi

Syllabi are available to current LSA students. IMPORTANT: These syllabi are provided to give students a general idea about the courses, as offered by LSA departments and programs in prior academic terms. The syllabi do not necessarily reflect the assignments, sequence of course materials, and/or course expectations that the faculty and departments/programs have for these same courses in the current and/or future terms.

Click the button below to view historical syllabi for MATH 684 (UM login required)

CourseProfile (ART)

The CourseProfile (ART) system, supported by the U-M Provostâ€™s 3rd Century Initiative through a grant to the Office of Academic Innovation, provides additional information about: course enrollments; academic terms and instructors; student academic profiles (school/college, majors), and previous, concurrent, and subsequent course enrollments.