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

CSE 396: Introduction to the Theory of Computation

This page refers to the Summer 2017 offering of CSE 396 only. The information on this page does not necessarily apply to every offering of CSE 396.

Summer 2017


Andrew Hughes

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, and MTH 142 Approved Computer Science, Computer Engineering, Bioinformatics/CS Majors Only

Valid XHTML 1.0 Transitional