Theory of Computation by Jim Hefferon, along with its companion answers to exercises, is a text for a one semester first undergraduate Computer Science theory course. It is Free. Use it as the main book, as a supplement, or for independent study.
Table of Contents
This shows the chapters and sections. For more, see the description or the text.
- Mechanical Computation
- Turing machines
- Church's Thesis
- Recursion
- General Recursion
- Topics: Turing machine simulator, Hardware, Game of Life, Ackermann's function is not primitive recursive, LOOP programs
- Background
- Infinity
- Cantor's correspondence
- Diagonalization
- Universality
- Halting problem
- Rice's theorem
- Computably enumerable sets
- Oracles
- Fixed point theorem
- Topics: Hilbert's hotel, Halting problem in wider culture, Self reproduction, Busy beaver
- Languages
- Languages
- Grammars
- Graphs
- Topics: BNF, Tree traversal
- Automata
- Finite state machines
- Nondeterminism
- Regular expressions
- Regular languages
- Languages that are not regular
- Minimization
- Pushdown machines
- Topics: Regular expressions in the wild, Myhill-Nerode theorem
- Computational complexity
- Big O
- Problem miscellany
- Problems, algorithms, and programs
- P
- NP
- Polytime reduction
- NP completeness
- Other classes
- Topic: RSA encryption, Good-enoughness, SAT solvers
- Back matter
- Review of strings
- Review of functions
- Review of propositional logic
- Supplemental notes
- Bibliography
- Index