3. Say whether each of i. - iv. is True or False. In each case briefly justify y

Question

3. Say whether each of i. - iv. is True or False. In each case briefly justify your answer i. There are infinitely many undecidable problems. ii. If L is decidable and J is undecidable than L U J is undecidable. iii. If L is decidable and J is undecidable than LnJis undecidable. iv. If J is reducible to K and K is recognizable then J is also recognizable. 4. Prove that the problem of deciding if a TM M ever writes the symbol 1 on its tape is You should do these problems using reduction s. 5. Prove that it is undecidable to determine if two TM's M and L accept the same languages You should do these problems using reductions.

Explanation / Answer

Solution:

The first question is done as per Chegg guidelines, please repost others.

3)

i)

True

ii)

True

Explanation:

The union of these two problems will be one big problem which is more complex, so it will be undecidable.

iii)

False

Explanation::

Since one of them is decidable the intersection between them will also be decidable.

iv)

True.

Explanation:

J is reducible to K means, J can also be solved in same time as K. which means true.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.