# 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.

**Note:**

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.

**Textbook(s)**
Title: Introduction to the Theory of Computation
Author(s): Michael Sipser
Publisher: Course Technology
Edition: 3rd
ISBN: 113318779X

**Pre-requisites:**

CS 220/CS 320L