CSE 531 Computational Complexity Notes

Some basic definition:

\mathcal{L}(M) = \{ x \in \Sigma^* : M \textrm{ accepts } x \}

Language: a language is a set of strings. If you have an alphabet, such as \Sigma, then \Sigma^* is the set of all words containing only the symbols in \Sigma. For example, \{0,1\}^* is the set of all binary sequences of any length.

Turing machine: A Turing machine is a 7-tuple, (Q, \Sigma,\Gamma,\delta, q_0,q_{\textrm{accept}},q_{\textrm{reject}}) where Q,\Sigma, \Gamma are all finite sets and

  1. Q is the set of states,
  2. \Sigma is the input alphabet not containing the blank symbol \textvisible,
  3. \Gamma is the tape alphabet, where \textvisiblespace \in \Gamma and \Sigma \seteq \Gamma,
  4. \delta: Q \times \Gamma \rightarrow Q \times \Gamma \{L,R\} is the transition function,
  5. q_0 \in Q is the start state,
  6. q_{\textrm{accept}} \in Q is the accept state, and
  7. q_{\textrm{reject}} \in Q is the reject state, where q_{\textrm{reject}} \neq q_{\textrm{accept}}