Introduction to Computation Theory

Graduate course, Department of Computer Science, Baylor University, 2022

This course is an introduction to the theory of computation. It covers formal models of computation, computability, complexity, and related topics. This course forms a foundation for much of the subsequent work/research you will do in computer science. As you’ll see, computation theory is fascinating because there are problems which we can describe simply which have not yet been solved.

This course will be taught online (Canvas. 202213 CSI 5310 OL1).

Here some extra information:

Javier OrduzBaylor University

Check the references to find the textbook, and please note: using another edition will probably be fine, but it may have different numbering of problems and exercises. I have seen students lose credit for using “international” versions that are mostly the same, except for the problems and exercises. Make sure you are doing the problems as assigned.

Bibliography and references

[1] Sipser, M. (2015). Introduction to the theory of computation (3rd ed.). Cengage Learning. ISBN-13: 978-1133187790. Amazon