Skip Navigation
search: People | Departments | Penn State | Web
Penn State mark
Penn State mark
University Bulletin
Graduate Degree Programs

These course descriptions are not being updated as of August 1, 2016. Current course descriptions are maintained in LionPATH.

Computer Science (CMPSC)

CMPSC 464 Introduction to the Theory of Computation (3) Computability/Complexity: finite automata, regular & context-free languages, Turing machines, Church-Turing Thesis, undecidability, reducibility, completeness, time/space complexity, P versus NP.

CMPSC 464 Introduction to the Theory and Computation (3)

CMPSC 464 introduces students to an essential part of theoretical computer science: how to define abstract mathematical models of computational devices (automata), how to characterize their computational power by studying the family of languages that they can recognize (formal languages), and what the limitations of even the most powerful computational devices are (computability). The course studies regular languages by means of deterministic and nondeterministic finite-state automata and regular expressions; it studies context-free languages through the use of context-free grammars and pushdown automata; and it studies computability by means of Turing machines and recursive and recursively-enumerable languages. The unsolvability of the halting problem for Turing machines is proved by a diagonalization argument, and this result is then used to show that various problems about languages are unsolvable, such as the problem of determining whether two context-free grammars generate the same language.

Finally, the concept of computational complexity is introduced, and the classes P and NP are defined. (Informally, the former class consists of problems that can be solved computationally in a manageable amount of time, and the latter consists of problems for which a proposed solution can be verified in a manageable amount of time.) The concept of an NP-complete problem is defined, and some specific problems are proved to be values to the variable of a Boolean formula that will make the formula true).


General Education: None
Diversity: None
Bachelor of Arts: None
Effective: Fall 2009
Prerequisite: CMPSC 465

Note : Class size, frequency of offering, and evaluation methods will vary by location and instructor. For these details check the specific course syllabus.

Search
CourseInfo

Look up course abbreviations

Course descriptions are stored in LionPATH, the University-wide student information system. Please visit the LionPATH Course Catalog to access current course descriptions. At that point, you will be leaving the University Bulletin website.



Skip Popular Searches
  1. Graduate Course Descriptions
  2. Graduate Programs
  3. Doctoral Degree Requirements
  4. Master's Degree Requirements
  5. Application and Admission Procedures
  6. Credit Certificate Programs
  7. General Information
  8. Tuition and Cost
  9. Intercollege
    Programs
  10. Academic Information and Procedures