CSE 318/CSE 409 (Introduction to the Theory of Computation)
Michael Sipser Introduction to the Theory of Computation
The course studies formal properties of computation. The course addresses the following questions:
- What is computation? (here is a short essay to this fundamental question)
- What kinds of well-defined problems (i.e., expressed in terms of inputs and outputs) can be solved by computation?
- What kinds of well-defined problems (i.e., expressed in terms of inputs and outputs) cannot be solved by computation?
Here is a cool video
that presents Turing machines, one of the central topics of the course.
Students will gain a deep understanding of the capabilities and limitations of computation. As a result, they will have a unique insight to questions grappling society today related to the AI Question and technological singularity, which will be addressed in the course.
The notion of computation including nondeterministic computation
Finite State Machines: finite automata and stack-based automata
The Church-Turing Thesis and the notion of algorithm
There will be homeworks and two tests.
Students choose between taking a final exam or working on a programming project aimed at improving their understanding of topics covered by the course.
Tests 50% (Test # 1: 25%, Test # 2: 25%)
Final Exam or Final Project 30%
Last update: Oct. 10 00:17:57 EDT