CSC 452/652/752: Theory of Computation

Spring 2025
Department of Computer Science
UNC Greensboro
Class Meetings: Mon/Wed 2:00-3:15, Petty Building Room 303

Instructor

Steve Tate
E-mail:
Office: 157 Petty Building
Office Hours: Mon/Wed 3:30-5:00 (or by appointment)
         Online meetings possible if arranged in advance via email

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.