CSE105 – Theory of Computability
Units: 4
Course Objectives:
This course gives a precise definition of the notion of an algorithm as well as developing a theory of automata and formal languages. The course stresses the understanding of the basic concepts and constructions.
NOTE: Repeat credit process for cross-reference courses: Students may receive credit for CSE 105 or Math 166. These courses have been cross-referenced, therefore, a petition is not required for using either course when completing major requirements. However, if you fail one of the courses listed about you should take the SAME COURSE for REPEAT CREDIT. If you use another course that is equivalent, the repeat credit is not automatic and you will need to petition for repeat credit.
Course Description:
An introduction to the mathematical theory of computability. Formal languages. Finite automata and regular expression. Push-down automata and context-free languages. Computable or recursive functions: Turing machines, the halting problem. Undecidability.
Format:
3 hours of lecture per week, 1 hour section per week, and 6 hours of outside preparation.
Prerequisites:
CSE 12 and CSE 21 or Math 15B or Math 100A or Math 103A or consent of the instructor.
Other restrictions:
Majors only. Credit not offered for both Math 166 and CSE 105. Equivalent to Math 166.
Example Textbook(s):
Elements of the Theory of Computation, Lewis and Papadimitriou.
Laboratory work:
Offered:
Three sections per year.
Resources
