Apr 23, 2024  
2023-2024 Undergraduate Catalog 
    
Catalog Navigation
  Catalog Home
  Archived Catalogs
  General Catalog Information
  Majors and Combined Degrees
  Minors, Certificates and Micro-Credentials
  Departments & Programs
  Courses
  UB Curriculum (General Education)
  Academic Policies and Procedures
  Academic Calendar
  Campus Facilities and Instructional Spaces
  Financial and Scholarship Information
  Admissions
  Student Records and Registration
  Academic Advising
  Learning Outside the Classroom
  Study Abroad
  myUB
  HUB Academic Advisement Report
  Accreditations
HELP
2023-2024 Undergraduate Catalog [ARCHIVED CATALOG]

CSE 396LR - 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.

Credits: 4

Grading
Graded (GRD)

Typically Offered:
Spring

Requisites:
Pre-Requisite: CSE 191  or MTH 311  and CSE 250 , and MTH 142  or MTH 139 . Computer Science, Computer Engineering, or Bioinformatics majors only. Students must complete a mandatory advisement session with their faculty advisor.