• Computation Theory

  1. P, NP, NPC, NP-hard
  2. Finite autmata, Regular Language.
     1. DFA, NFA
     2. Regular language to NFA
  3. Pushdown automata, Context-Free Language.
  4. Turing machines, Recursively enumerable language
     1. Turing-Church thesis
  5. Slovable, unsolvable

Recognize / Accept:

If A is the set of all strings that machine M accepts, we say that A is the language of machine M and write L(M ) = A. We say that M recognizes A or that M accepts A.

Decide:

These machines are called deciders because they always make a decision to accept or reject. A decider that recognizes some language also is said to decide that language.