CSE 105 - Theory of Computability

Units: 

 4

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.

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.

Prerequisites: 

CSE 12, CSE 15L, CSE 21 or Math 154 or Math 184A or Math 100A or Math 103A; restricted to SO, JR, SR standing. Graduate students will be allowed as space permits. Please see Prerequisites page

Other Restrictions: 

Credit not offered for both Math 166 and CSE 105. Equivalent to Math 166.

Offered: 

Three sections per year.