Note that each language is in exactly one category. Languages: i. { G | For some

Question

Note that each language is in exactly one category.

Languages:


i. { G | For some integer n, G is a graph with n vertices and G has no clique of size n-2 }


Note: H-BAR is the complement of the halting problem.

ii. { M | M accepts exactly 5 inputs }

iii. { M | M accepts greater than 5 inputs }

iv. {(M,w) | M accepts w within 5 steps of the M(w) computation }

v. (H-BAR)-{(M,w) | M halts w within 5 steps of the M(w) computation }
Note: H-BAR is the complement of the halting problem, and - means set subtraction here.


Categories:

A. DECIDABLE LANGUAGES

B. UNDECIDABLE and RECOGNIZABLE LANGUAGES

C. UNDECIDABLE and NOT RECOGNIZABLE LANGUAGES but the complement is RECOGNIZABLE

D. UNDECIDABLE LANGUAGES for which both it and its complement are NOT RECOGNIZABLE

Match each one to a category. Also, can you give me some insight on your intuition.

Explanation / Answer

i. This language is decidable. We can create a machine which uses any algorithm for detecting cliques. Simply do a brute force, select n-1 vertices and check whether they have a n-1 clique then we complete the job in finite time. ii is un recognizable meaning undecidable hence also not Compliment recognizable. iii. is undecidable but recognizable but not Compliment recognizable. (A language which is not decidable is also not compliment recognizable as if L>= HP iff ~L >= ~HP hence) we cannot determine in finite time ever to check whether 5 inputs are accepted or not. We can prove that this is undecidable. You can use the Rice's Theorem to prove that both are undecidable As both the properties are language properties and are non trivial hence undecidable Now we can see that a is is not monotone property. Hence by Rice's theorem hence a is not recognizable but the b property is monotone hence Rices thm does not apply infact it is recognizable to construct a machine to do this we will create a machine which simulates a huge number of inputs at the same time in parallel on a machine with a 2D tape giving 1 execution time for inputs one by one but in a seq like this 1,1,2,1,2,3,1,2,3,4,1,2,3,4,5,1,2,3,4,5,6,1..... So that we can effectively compute the inputs when we see that 5 ips are accepted we accept and halt then if 5 ips are not accepted then it will keep on executing and then will not stop hence rejecting the machine. iv. Also decidable as we simply use a universal turing machine to simulate M on w for 5 steps. v. I am unable to understand the problem is it HBAR - {..} or {..} {M,w|M halts on w in 5 steps} : decidable HBAR - {M,w|M halts on w in 5 steps} : not decidable and not recognizable same as HBAR as if it is anything else so would HBAR .Hence message if you need any help

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

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