| |
Jul 30, 2025
|
|
|
|
|
CSCI 6050 - Theory of Computation
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.
Prerequisite or Corequisite: Prerequisites: None.
When Offered: SPRING ALTERNATE YEARS
Co-Listed: CSCI 4050
Graded: GRADED
Credit Hours: 4
Add to Portfolio (opens a new window)
|
|
