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), insolvability 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 CS 220/CS 320L during fall 1989 or later. It may be used as a theoretical elective by other computer science majors.


CS 220/CS 320L

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

This page was last modified on September 21, 2018
© 2018 University of Massachusetts Boston

Template by OS Templates