MHB Show that the languages are undecidable

  • Thread starter Thread starter mathmari
  • Start date Start date
AI Thread Summary
The discussion focuses on proving the undecidability of the languages H ∩ U and H ∪ U, where H is the Halting Problem and U is the Universal Language. It is established that U is a subset of H, leading to the conclusions that H ∩ U equals U and H ∪ U equals H. Since both U and H are known to be undecidable, it follows that H ∩ U and H ∪ U are also undecidable. The participants confirm the correctness of this reasoning.
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

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 Langauge 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)
 
Physics news on Phys.org
You are correct.
 
Evgeny.Makarov said:
You are correct.

Thank you! (Smile)
 

Similar threads

Replies
12
Views
4K
Replies
5
Views
2K
Replies
17
Views
4K
Replies
5
Views
1K
Replies
5
Views
1K
Replies
6
Views
2K
Back
Top