--- title: Theory of Computation description: This mathematical branch of computer science explores what can be computed and how efficiently. You will understand automata theory, formal languages, computability, and complexity classes, helping you grasp the fundamental limits of computers and algorithms. category: programming-tech subcategory: computer-science difficulty: beginner, intermediate, advanced url: /subject/theory-of-computation --- # Theory of Computation This mathematical branch of computer science explores what can be computed and how efficiently. You will understand automata theory, formal languages, computability, and complexity classes, helping you grasp the fundamental limits of computers and algorithms. ## Available Resources 3 Books • 5 Courses • 4 Websites ## Websites ### 1. NFA to DFA Converter Browser-based simulator by Kyle Dickerson for building DFAs, NFAs, and pushdown automata, then running inputs through them singly or in bulk. Useful for checking by hand whether a machine you designed accepts the right language. **Difficulty:** Beginner | **Price:** Free **Link:** https://automatonsimulator.com/ **Tags:** automata, finite-automata, pushdown-automata, simulator, theory-of-computation ### 2. theoryofcomputing.org Theoryofcomputing.org is a practical resource hub for theory of computation, featuring lecture notes, tutorials, and problem sets on automata, formal languages, computability, and complexity to help learners build intuition and tackle exercises. **Difficulty:** Intermediate | **Language:** English | **Price:** Free **Link:** https://theoryofcomputing.org **Tags:** websites, technology-computer-science, computer-sciences ### 3. complexityzoo.net Complexity Zoo is a comprehensive online catalog of computational complexity classes, providing formal definitions, properties, and the known relationships (inclusions and separations) among classes. It covers hundreds of classes—from P, NP, PSPACE, and EXP to probabilistic, quantum, counting, and nonuniform varieties—along with their definitions and key results, making it a core reference for Theory of Computation. **Difficulty:** Intermediate | **Language:** English | **Price:** Free **Link:** https://complexityzoo.net **Tags:** websites, technology-computer-science, computer-sciences ### 4. cstheory.stackexchange.com A Q&A community for theory of computation, covering topics like automata, algorithms, complexity, cryptography, and related areas of theoretical computer science. Users ask, answer, vote, and tag questions to build a curated knowledge base. **Difficulty:** Intermediate | **Language:** English | **Price:** Free **Link:** https://cstheory.stackexchange.com **Tags:** websites, technology-computer-science, computer-sciences ## Courses ### 1. Algorithmic Lower Bounds: Fun with Hardness Proofs (MIT 6.890) **Author:** Erik Demaine Techniques for proving problems computationally hard: NP-hardness reductions, gadget design, games and puzzles, PSPACE-completeness, inapproximability and fixed-parameter hardness. Includes 23 lecture videos, lecture notes, and problem sets with solutions. Afterwards you can construct reductions showing a problem likely has no efficient algorithm. **Difficulty:** Advanced | **Price:** Free **Link:** https://ocw.mit.edu/courses/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/ **Tags:** computational-complexity, np-hardness, reductions, lower-bounds, inapproximability ### 2. Introduction to Algorithms (MIT 6.006) **Author:** Erik Demaine, Jason Ku, Justin Solomon Modeling computational problems and solving them with core algorithms and data structures: sorting, hashing, binary trees, heaps, graph search, shortest paths and dynamic programming. 32 lecture videos, notes, problem sets and exams with solutions teach asymptotic analysis and algorithm design. **Difficulty:** Intermediate | **Price:** Free **Link:** https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/ **Tags:** data-structures, asymptotic-analysis, graph-algorithms, dynamic-programming, sorting ### 3. Theory of Computation Learn computability theory with Kamala Krithivasan's Theory of Computation course. Explore fundamental concepts and problem-solving! **Difficulty:** Advanced | **Price:** Free **Link:** https://nptel.ac.in/courses/106105163 **Tags:** theory-of-computation, automata, turing-machines, formal-languages, decidability ### 4. Theory of Computation (MIT 18.404J) **Author:** Michael Sipser Sipser's course on automata, computability and complexity: regular and context-free languages, decidability, reducibility, the recursion theorem, time and space complexity, NP-completeness, hierarchy theorems, probabilistic computation and interactive proofs. 25 lecture videos, slides, problem sets and exams support rigorous proof-based study. **Difficulty:** Intermediate | **Price:** Free **Link:** https://ocw.mit.edu/courses/18-404j-theory-of-computation-fall-2020/ **Tags:** automata-theory, computability, decidability, complexity-theory, np-completeness ### 5. Dynamic Systems and Control (MIT 6.241J) **Author:** Emilio Frazzoli, Munther Dahleh Analysis and control of linear time-invariant systems modeled by ordinary differential equations: state-space models, input-output response, feedback interconnections, stability and performance. Provides lecture notes, the full open textbook, and problem sets with solutions for designing controllers with guaranteed properties. **Difficulty:** Advanced | **Price:** Free **Link:** https://ocw.mit.edu/courses/6-241j-dynamic-systems-and-control-spring-2011/ **Tags:** linear-systems, state-space, stability, feedback-control, robust-control ## Books ### 1. Introduction to the Theory of Computation **Author:** Michael Sipser The standard undergraduate text on automata, context-free languages, Turing machines, decidability, and complexity classes including NP-completeness. Its proofs are written out in full, so readers learn to construct formal arguments about what machines can compute. **Difficulty:** Intermediate | **Language:** English | **Price:** Paid **Link:** https://www.amazon.com/dp/053494728X?tag=edmonddante07-20 **Tags:** books, technology-computer-science, computer-sciences ### 2. Computability and Logic **Author:** George S. Boolos, John P. Burgess, Richard C. Jeffrey A logic text that builds from Turing machines and recursive functions up to Gödel's incompleteness theorems, then adds optional chapters on model theory and Ramsey's theorem. Assumes no prior mathematical background beyond willingness to follow proofs. **Difficulty:** Intermediate | **Language:** English | **Price:** Paid **Link:** https://www.amazon.com/dp/0521007585?tag=edmonddante07-20 **Tags:** books, technology-computer-science, computer-sciences ### 3. Automata Theory **Author:** John E. Hopcroft, Jeffrey D. Ullman The 1979 Hopcroft and Ullman classic on formal languages and machine models: regular and context-free languages, Turing machines, undecidability, and an introduction to computational complexity. Terse and proof-dense, aimed at readers comfortable with mathematical argument. **Difficulty:** Intermediate | **Language:** English | **Price:** Paid **Link:** https://www.amazon.com/dp/020102988X?tag=edmonddante07-20 **Tags:** books, technology-computer-science, computer-sciences --- *This content is part of Dantes.io - Your Treasure Map to Knowledge* *Curated by humans at Dantes.io. Personal study use welcome; republishing this curation requires permission (team@dantes.io).* View this page online: https://dantes.io/subject/theory-of-computation