# Theory Of Computation

## CSCI-6050

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.

3 credits
Prereqs:
none

# 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 |  |  |
2024 |  |  |
2023 |  |  |
2022 |  |  |
2021 |  |  |
2020 |  |  |
2019 |  |  |
2018 |  |  |
2017 |  |  |
2016 |  |  |

2015

Computability & Complexity (3c)

- Eugene Eberbach

Seats Taken: 2/30

2014

Computability & Complexity (3c)

- Mark K Goldberg

Seats Taken: 18/60

2013

Computability & Complexity (3c)

- Mark K Goldberg

Seats Taken: 38/60

2012

Computability & Complexity (3c)

- Mark K Goldberg

Seats Taken: 31/60

2011

Computability & Complexity (3c)

- Mark K Goldberg

Seats Taken: 19/60

2010

Computability & Complexity (3c)

- Mark K Goldberg

Seats Taken: 33/60

2009

Computability & Complexity (3c)

- Eugene Eberbach

Seats Taken: 13/100

Computability & Complexity (3c)

- Mark K Goldberg

Seats Taken: 33/60

2008

Computability & Complexity (3c)

- Mark K Goldberg

Seats Taken: 26/60

2007

Computability & Complexity (3c)

- Eugene Eberbach

Seats Taken: 19/100

Computability & Complexity (3c)

- Mark K Goldberg

Seats Taken: 15/60

2006

Computability & Complexity (3c)

- Mark K Goldberg

Seats Taken: 25/60

2005

Computability & Complexity (3c)

- Robert E. LaBarre

Seats Taken: 8/956

Computability & Complexity (3c)

- Mark K Goldberg

Seats Taken: 20/60

2004

Computability & Complexity (3c)

- Robert E. LaBarre

Seats Taken: 9/139

Computability & Complexity (3c)

- Mark K Goldberg

Seats Taken: 25/40

2003 |  |  |

2002

Computability & Complexity (3c)

Seats Taken: 21/2100

2001

Computability & Complexity (3c)

- Mark K Goldberg

Seats Taken: 29/40

2000 |  |  |
1999 |  |  |
1998 |  |  |