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

CSE 396: Introduction to the Theory of Computation

Introduction to the Theory of Computation

Covers machine models and formal specifications of the classes of computational problems they can solve. The central concepts are the Turing machine and the classes of decidable and computably enumerable languages. The Halting Problem and other natural problems are shown to be undecidable by Turing machines, implying that they are undecidable by high-level programming languages or any other known computational model. Finite automata, which are Turing machines without external memory, are shown to correspond to the class of regular languages. The course also covers regular expressions, time and space complexity of Turing machines, reducibility between problems, and NP-completeness.

None presently available.

CSE 191, CSE 250 CSE 250

Course Instances
Semester Section Title Instructor Credit Hours Enrolled
Spring 2014 LR Intro Theory Of Computatn Staff 4 0/100
Summer 2013 LR Intro Theory Of Computatn Andrew Hughes 4 15/25
Spring 2013 LR Intro Theory Of Computatn Dr. Alan L. Selman 4 89/100
Summer 2012 LR Intro Theory Of Computatn Andrew Hughes 4 9/25
Spring 2012 LR Intro Theory Of Computatn Dr. Alan L. Selman 4 93/96
Spring 2011 LR Intro Theory Of Computatn Dr. Alan L. Selman 4 96/96
Spring 2010 LR Intro Theory Of Computatn Dr. Kenneth W. Regan 4 68/100
Spring 2009 LR Intro Theory Of Computatn Dr. Alan L. Selman 4 36/40
Fall 2008 LR Intro Theory Of Computatn Dr. Alan L. Selman 4 50/90
Spring 2008 LR Intro Theory Of Computatn Dr. Alan L. Selman 4 52/65
Fall 2007 LR Intro Theory Of Computatn Dr. Kenneth W. Regan 4 35/90
Spring 2007 LR Intro Theory Of Computatn Dr. Alan L. Selman 4 55/65
Fall 2006 LR Intro Theory Of Computatn Dr. Alan L. Selman 4 48/90
Spring 2006 LR Intro Theory Of Computatn Dr. Jinhui Xu 4 53/94
Fall 2005 LR Intro Theory Of Computatn Maurice Jansen 4 46/90
Spring 2005 LR Intro Theory Of Computatn Dr. Jinhui Xu 4 43/94
Fall 2004 LR Intro Theory Of Computatn Dr. Alan L. Selman 4 51/90
Spring 2004 LR Intro Theory Of Computatn Dr. Alan L. Selman 4 51/94
Fall 2003 LR Intro Theory Of Computatn Dr. Kenneth W. Regan 4 57/90
Spring 2003 LR Intro Theory Of Computatn Dr. Alan L. Selman 4 91/94
Fall 2002 LR Intro Theory Of Computatn Dr. Alan L. Selman 4 94/100
Spring 2002 LR Intro Theory Of Computatn Dr. Kenneth W. Regan 4 83/90
Fall 2001 LR Intro Theory Of Computatn Dr. Kenneth W. Regan 4 80/100
Spring 2001 LR Intro Theory Of Computatn Dr. Alan L. Selman 4 94/94
Fall 2000 LR Intro Theory Of Computatn Dr. Alan L. Selman 4 71/100
Spring 2000 LR Intro Theory Of Computatn Dr. Alan L. Selman 4 90/92
Fall 1999 LR Intro Theory Of Computatn Dr. Kenneth W. Regan 4 60/75
Spring 1999 LR Intro Theory Of Computatn Dr. Alan L. Selman 4 87/90
Valid XHTML 1.0 Transitional