TC

  • Homework 3
  • \mathbf{R}=\mathbf{RE}\cap \mathbf{coRE}
  • characterization of \mathbf{RE} (and \mathbf{coRE})

April 21, 2026

Recap on notation

M Turing machine

  • M(x)
  • M(x)\!\downarrow
  • How many TMs?
  • Universal Turing Machine U

  • From Homework 3
    • Examples of TMs
    • Equivalent models

From TMs to pseudocode

  • sequential composition
  • if (...) then ... else ...
  • while(...) ...

\mathbf{R}=\mathbf{RE}\cap \mathbf{coRE}

(\subseteq) last class

(\supseteq) how?




Corollary 1 \mathtt{K}=\{x \mid M_x(x)\!\downarrow\}\in \mathbf{RE}\setminus\mathbf{R} and \mathtt{\overline K}\in \mathbf{RE}\setminus\mathbf{R}

Theorem 1 A\in \mathbf{RE} \Longleftrightarrow there exist B\in \mathbf{R} s.t. A=\{x\ \mid \exists t\ \langle x,t\rangle\in B\}

Proof. (\Longleftarrow) there exist B\in \mathbf{R} s.t. A=\{x\ \mid \exists t\ \langle x,t\rangle\in B\}, why A\in \mathbf{RE}?


(\Longrightarrow) A\in \mathbf{RE}, what is a B\in \mathbf{R} s.t. A=\{x\ \mid \exists t\ \langle x,t\rangle\in B\}?





Theorem 2 A\in \mathbf{coRE} iff there exist B\in \mathbf{R} s.t. A=\{x\ \mid \forall t\ \langle x,t\rangle\in B\}

Proof. similar