- #1
mathmari
Gold Member
MHB
- 4,984
- 7
Hey! 
Let $H$ be the Halting Problem and $U$ the Universal Language. I want to show that the languages $H\cap U$ and $H\cup U$ are undecidable.
We have the following:
The Universal language is $U=\{(x,y) \mid M_x(y) \text{ accepts }\}$ and the Halting Problem is the language $H=\{(x,y) \mid M_x(y) \text{ halts }\}$.
When a TM halts, it can either accept or reject the input. So, we have that $U\subseteq H$, or not? (Wondering)
Therefore, we have that $H\cap U=U$ and $H\cup U=H$.
Since $U$ and $H$ are undecidable, it follows that the languages $H\cap U$ and $H\cup U$ are undecidable. Is this correct? (Wondering)
Let $H$ be the Halting Problem and $U$ the Universal Language. I want to show that the languages $H\cap U$ and $H\cup U$ are undecidable.
We have the following:
The Universal language is $U=\{(x,y) \mid M_x(y) \text{ accepts }\}$ and the Halting Problem is the language $H=\{(x,y) \mid M_x(y) \text{ halts }\}$.
When a TM halts, it can either accept or reject the input. So, we have that $U\subseteq H$, or not? (Wondering)
Therefore, we have that $H\cap U=U$ and $H\cup U=H$.
Since $U$ and $H$ are undecidable, it follows that the languages $H\cap U$ and $H\cup U$ are undecidable. Is this correct? (Wondering)