Theory of Computation topics

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:

Practice questions (MCQ) on Theory of Computation

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

Type 2

Type 1

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.