COMS 3310: Theory of Computing
(Cross-listed with LING 3310).
Credits: 3. Contact Hours: Lecture 3, Discussion 1.
Prereq: Minimum of C- in (COMS 2280; MATH 1660; ENGL 2500); (COMS 2300 or CPRE 3100)
Models of computation: finite state automata, pushdown automata and Turing machines. Study of grammars and their relation to automata. Limits of digital computation, unsolvability and Church-Turing thesis. Relations between classes of languages.
(Typically Offered: Fall, Spring)