# CSE 318/CSE 409 (Introduction to the Theory of Computation)

## Spring 2018

### Texts

Required:

Michael Sipser * Introduction to the Theory of Computation
(Second Edition)*

### Description

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.

### topics covered

The notion of computation including nondeterministic computation
Finite State Machines: finite automata and stack-based automata
Turing machines
Decidable Languages
The Church-Turing Thesis and the notion of algorithm

### Course work

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.

### Grading

**Tests** 50% (Test # 1: 25%, Test # 2: 25%)

**Final Exam or Final Project** 30%

**Homework:** 20%

Last update: *Oct. 10 00:17:57 EDT
2017*