CSC 452/652: Theory of Computation

Spring 2020
Department of Computer Science
UNC Greensboro
Class Meetings: Mon/Wed 3:30-4:45, Moore Nursing Building Room 329

Instructor

Steve Tate
Office: 157 Petty Building
Office Hours: Mon/Wed 1:30-3:00
E-mail:

Overview

In this class we explore the most fundamental question in computer science: What does it mean to compute something? This includes exploring issues such as processes/models that can mechanize computations, problems that can and cannot be solved with different models of computation, and fundamental limitations that restrict what problems can be solved computationally. While the focus of an algorithms class is on how fast problems can be solved by modern computers, this class digs deeper into the fundamental question of what problems are possible to solve in various computational models. The approach in this class is formal, using precise mathematical models and a significant amount of formal reasoning and mathematical proofs.