UB - University at Buffalo, The State University of New York Computer Science and Engineering

CSE 596: Introduction to the Theory of Computation

Introduction to the Theory of Computation

Turing machines, RAMs, decidable and computably enumerable sets, partial computable functions; Church-Turing thesis; undecidable problems, diagonalization, Recursion Theorem, Rice's Theorem, Kleene Normal Form Theorem. Time and space complexity bounds, complexity classes, Savitch's Theorem, NL = coNL. NP-completeness, Cook-Levin Theorem, polynomial hierarchy, complete problems for other complexity classes.

Ph.D.:

None.

M.S.:

This course does not fulfill core area (depth) or core course (breadth) requirements.

Discrete mathematics and/or courses in mathematics that involve proofs of theorems. Undergraduate course in finite automata theory is recommended.

Course Instances
Semester Section Title Instructor Credit Hours Enrolled
Fall 2016 LEC Intro Theory Of Computatn Dr. Kenneth W. Regan 3 4/60
Fall 2015 LEC Intro Theory Of Computatn Dr. Kenneth W. Regan 3 18/60
Fall 2014 LEC Intro Theory Of Computatn Dr. Kenneth W. Regan 3 32/60
Fall 2013 LEC Intro Theory Of Computatn Dr. Alan L. Selman 3 48/60
Fall 2012 LEC Intro Theory Of Computatn Dr. Kenneth W. Regan 3 29/60
Fall 2011 LEC Intro Theory Of Computatn Dr. Alan L. Selman 3 41/60
Fall 2010 LR Intro Theory Of Computatn Dr. Alan L. Selman 3 26/60
Fall 2009 LR Intro Theory Of Computatn Dr. Alan L. Selman 3 29/60
Fall 2008 LR Intro Theory Of Computatn Dr. Kenneth W. Regan 3 17/60
Fall 2007 LR Intro Theory Of Computatn Dr. Alan L. Selman 3 24/60
Fall 2006 LR Intro Theory Of Computatn Dr. Kenneth W. Regan 3 21/21
Fall 2005 LR Intro Theory Of Computatn Dr. Alan L. Selman 3 30/60
Fall 2004 LR Intro Theory Of Computatn Dr. Kenneth W. Regan 3 30/60
Spring 2004 LR Intro Theory Of Computatn Dr. Kenneth W. Regan 3 0/ 0
Fall 2003 LR Intro Theory Of Computatn Dr. Alan L. Selman 3 18/60
Spring 2003 LR Intro Theory Of Computatn Dr. Kenneth W. Regan 3 33/75
Spring 2002 LR Intro Theory Of Computatn Dr. Alan L. Selman 3 41/75
Spring 2001 LR Intro Theory Of Computatn Staff 3 15/75
Fall 1999 LR Intro Theory Of Computatn Dr. Alan L. Selman 3 43/90
Valid XHTML 1.0 Transitional