# Theory Of Computation

## CSCI-4050

This course covers the formal foundations of computability and complexity. We aim to answer fundamental questions about what problems can be solved and what problems cannot be solved, and what problems can be solved given our limited resources. Topics include: the Church-Turing thesis; variations of Turing Machines; decidability; the Halting Problem; reducibility; the Recursion Theorem; time and space complexity; intractability; NP-completeness; and Cook’s theorem. We will also discuss some emerging and unconventional computing models.

4 credits
Cross-listed with:
CSCI-6972 Topics in CSCI
Prereqs:
CSCI-2300 Introduction To Algorithms
and
CSCI-2200 Foundations Of Computer Sci

# Past Term Data
Offered
Not Offered
Offered as Cross-Listing Only
No Term Data
Simple View
Detailed View

| Spring | Summer | Fall
--- | --- | --- | ---
| (Session 1) | (Session 2) |
2026 |  |  |

2025

Theory Of Computation (4c)

- Stacy Elizabeth Patterson

Seats Taken: 13/30

2024 |  |  |
2023 |  |  |
2022 |  |  |
2021 |  |  |
2020 |  |  |
2019 |  |  |
2018 |  |  |
2017 |  |  |
2016 |  |  |
2015 |  |  |

2014

Comput. & Complexity (4c)

- Mark K Goldberg

Seats Taken: 8/60

2013

Comput. & Complexity (4c)

- Mark K Goldberg

Seats Taken: 16/60

2012

Comput. & Complexity (4c)

- Mark K Goldberg

Seats Taken: 11/60

2011

Comput. & Complexity (4c)

- Mark K Goldberg

Seats Taken: 11/60

2010

Comput. & Complexity (4c)

- Mark K Goldberg

Seats Taken: 12/60

2009

Comput. & Complexity (4c)

- Mark K Goldberg

Seats Taken: 8/60

2008

Comput. & Complexity (4c)

- Mark K Goldberg

Seats Taken: 5/60

2007

Comput. & Complexity (4c)

- Mark K Goldberg

Seats Taken: 10/60

2006

Comput. & Complexity (4c)

- Mark K Goldberg

Seats Taken: 9/60

2005

Comput. & Complexity (4c)

- Mark K Goldberg

Seats Taken: 3/60

2004

Comput. & Complexity (4c)

- Mark K Goldberg

Seats Taken: 6/20

2003

Comput. & Complexity (4c)

- Mark K Goldberg

Seats Taken: 4/20

2002

Comput. & Complexity (4c)

- Mark K Goldberg

Seats Taken: 4/20

2001 |  |  |
2000 |  |  |
1999 |  |  |

1998

Computability (4c)

- Robert F McNaughton

Seats Taken: 60/70