HomeAcademicsCourses → CS420

Introduction to the Theory of Computation (3 credits)

Introduction to theoretical aspects of computing including models of computation, inherent limits on computation, and feasible computation. Topics studied will include definition of computable functions (recursive functions, functions computable by Turing machines, functions computable in a programming language), unsolvability of the halting problem and related problems, the classes P and NP, finite automata, and context-free grammars.


This course is required for all computer science majors who took CS320L during fall 1989 or later. It may be used as a theoretical elective by other computer science majors.



Title: Introduction to the Theory of Computation
Author(s): Michael Sipser
Publisher: Course Technology
ISBN: 0534950973

This page was last modified on August 18, 2007
© 2007 University of Massachusetts Boston

Template by OS Templates