# Theory of Computation topics

Get FREE domain for 1st year and build your brand new site

In this article, we have list all topics in Theory of Computation including Advanced Research Topics like Super Recursive Algorithms. This list is useful for all students at any level (B. Tech, M. Tech, PhD) to get a good idea of how to get started with Theory of Computation.

Theory of Computation is mainly divided into 4 components:

- Type 3
- Type 2
- Type 1
- Type 0

We have listed the important topics in each component. Important topics in Theory of Computation are:

# Introductory topics

- Introduction to Theory of Computation
- Chomsky Hierarchy
- Automata theory
- Computability theory
- Complexity theory
- Basic techniques for Proof
- Direct Proof
- Constructive Proof
- Nonconstructive Proof
- Proof by Contradiction
- Pigeon Hole Principle
- Proof by Induction

- Applications of Theory of Computation

# Type 3

- Regular Languages
- Finite Automata
- Deterministic finite automata (DFA)
- Nondeterministic finite automata (NFA)
- Equivalence of DFAs and NFAs
- Regular operations
- Regular expressions
- Equivalence of regular expressions and regular languages
- Pumping Lemma for Regular Languages (with proof)
- Pumping Lemma in Theory of Computation
- Pumping Lemma Questions
- Higman's Theorem
- Dickson's Theorem

# Type 2

- Context Free grammars
- Context Free Languages
- Context Free Grammar (CFG) for Chemistry
- Context free grammar (CFG) for Balanced Parentheses
- Applications of Context Free Grammar
- Regular Languages are Context Free Languages
- Chomsky normal form
- Pushdown Automata
- Pushdown Automata for 0^N 1^N
- Equivalence of Pushdown Automata and Context Free grammars
- Pumping lemma for Context Free languages

# Type 1

- Context Sensitive Grammar (CSG)
- Context Sensitive Language (CSL)
- Grammar for a^N b^N c^N
- Linear Bounded Automaton

# Type 0

- One Tape Turing machine
- Multi Tape Turing machines / K tape Turing Machine
- Non Deterministic Turing Machine
- Recursively Enumerable Languages
- Church Turing Thesis
- Limitations of Church Turing Thesis
- Halting Problem

# Decidable and Undecidable Languages

- Decidability
- Undecidability
- Countable sets
- Rice's Theorem
- Enumerability
- Most languages are not enumerable
- Relationship between decidable and enumerable languages
- A language A such that both A and A' are not enumerable

# Advance topics

- Halting Turing Machine
- Recursive Language
- Natural Languages
- Linear Context Free Rewriting Systems
- Definition of Algorithm in Theory of Computation
- Modern Computing Devices and Turing Machine
- Quantum Computers and Turing Machine
- Molecular Computer and Turing Machine
- Godel Incompleteness Theorem
- Super Recursive Algorithms
- Inductive Turing Machine
- Inductive Turing Machine + Structured Memory
- Inductive Turing Machine + Structured Rules (control device)
- Inductive Turing Machine + Structured Head (Operating Device)

- Extended Church Turing Thesis

With this article at OpenGenus, you must have a strong idea of the different topics in Theory of Computation you should have an idea of.