I found in some exercise in computation the following step: enter image description here enter image description here

I can't understand why is it equal terms, based of what I know about De morgan's law:

  1. OR should be replaced by AND
  2. where $w=\varepsilon$ come from

Let $\Sigma$ be the alphabet on which $A_{TM}$ is defined over, and assume w.l.o.g that:

  1. $A_{TM}\cup \overline{A_{TM}} = \Sigma^*$, and
  2. $0, 1 \notin\Sigma.$

The set $J$ can be written as:

$$ J = \{0\}\cdot A_{TM} \ \cup \{1\}\cdot \overline{A_{TM}} $$ where $J$ is defined over the alphabet $\Sigma \cup \{ 0, 1\}$. Now, using De morgan's law, it holds that: $$ \overline{J} = \overline{\{0\}\cdot A_{TM}} \ \ \cap \overline{\{1\}\cdot \overline{A_{TM}} } \\ $$ $$ =\left(\{w: \text{ $w \neq \sigma\cdot u$, $\sigma\in\{0, 1\}$ and $u\in \Sigma^*$} \} \cup \{0\}\cdot \overline{A_{TM}} \ \cup \{1\}\cdot \Sigma^*\right) \ \cap \\ \left(\{w: \text{ $w \neq \sigma\cdot u$, $\sigma\in\{0, 1\}$ and $u\in \Sigma^*$} \} \cup \{1\}\cdot A_{TM} \ \cup \{0\}\cdot \Sigma^*\right) \\ $$ $$ = \{w: \text{ $w \neq \sigma\cdot u$, $\sigma\in\{0, 1\}$ and $u\in \Sigma^*$} \} \cup \left( \left[\{0\}\cdot \overline{A_{TM}} \ \cup \{1\}\cdot \Sigma^* \right] \cap \left[ \{1\}\cdot A_{TM} \ \cup \{0\}\cdot \Sigma^*\right] \right) $$

$$ = \{w: \text{ $w \neq \sigma\cdot u$, $\sigma\in\{0, 1\}$ and $u\in \Sigma^*$} \} \cup \left( \{ 0\}\cdot \overline{A_{TM}} \cup \{ 1\}\cdot A_{TM} \right) $$

So, we have that $w \in \overline{J}$ iff $w$ does not encode a bit followed by a word of the form $\langle M, w \rangle$, or $w = 1x$ for some $x \in A_{TM}$ or $w = 0y$ for some $y \in \overline{A_{TM}}$.

Finally, note that they're implicitly assuming w.l.o.g that every nonempty word in $\{0, 1\}\cup \Sigma^*$ is of the form "$\text{bit} \cdot \langle M, w\rangle$". This assumption is okay, as checking whether a word respects some encoding can be easily done by a TM.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.