Computability

CPSC 513/601.08: Computability

About This Course

Computer Science 513 is a fourth-year undergraduate course in the theory of computation offered by the Department of Computer Science at the University of Calgary. It is an optional course, intended primarily for computer science majors. However, students in other programs — notably including students in mathematics programs — might also find this to be of interest.

In 2024 a graduate course — CPSC 601.08 — will also be available. This will share lectures with CPSC 513 but will have different assessment — replacing tests with a project.

Quite a bit of the material, considered here, comes from a time before computers were widely available (or, sometimes, even known about) and before there was a discipline called “computer science”, at all. These early studies had a significant impact on the study of efficient computation — “computational complexity theory” — that followed. Thus this course provides some of the early history of computer science — and it includes material that influenced work in at least one other significant part of this discipline.

In Fall 2024, one section (for both the undergraduate and the graduate course) is available:

L01, lectures 9:30–10:45am, Tuesdays and Thursdays, in HNSC 124A.

This is a flipped course: Students will be expected to complete a reading assignment (or watch a video) before attending each lecture. The lecture time will be used to solve a problem that is related to the assigned reading and makes use of material introduced in it.

This course will have a D2L course site which will be used for course communication and reporting of grades. All material, supplied to students for course work, will be made available on the D2L site. The page that you are reading now (and other pages linked to it) includes a subset of this material that can also be accessed by people outside this course. They pages are certainly “under construction” at this point, and they describe the course as it will be offered in Fall 2024.

Course Outline

This sentence is a link to the course outline for CPSC 513. This sentence is a link to the course outline for CPSC 601.08.

Lectures

Additional Course Material

Additional References

CPSC 601.08 students will be required to read beyond the material provided on the course web site, when completing the course project. On the other hand, it is not required for students in either CPSC 513 or CPSC 601.08 to use material, that is not provided on the course web site, to do well on course assignments and tests.

With that noted, each of the following books are available, as ebooks, to University of Calgary students (and links to these ebooks are given below) — and each of these could be used as the textbook in this course.