(3) Prove that the following language is undecidable L {< M, w> M accepts exactly three...

Question

Question

Answer 1

Answer #1

Suppose there is an algorithm say Decideacceptthree that correctly decide the language l.

Decidehalt is constructed as follows:

1) input is <M,w>

Where M is a code for turing machine and w is a string.

2) code for the turing machine are as given below:

Input is string x and x is exactly one of three string "a","b","c".

run M on input w.

If M reject w than reject otherwise accept when x is exactly one of the three strings "a","b","c".

Put this Mw to Decideacceptthree if accept than accept.

If Decideacceptthree reject than reject.

If language Mw contain exactly three strings than M accepts w.so Decideacceptthree (Mw) accept when M accepts w.

If language of Mw is empty string than M does not accepts w.

So Decidehalt decide A_TM.

As we know that A_TM is undecidable so Decidehalt can not be exist.

so language l is undecidable.

Answer 2

Similar Homework Help Questions

3. Let T = {< M > | m accepts w" when it accepts w. }....

3. Let T = {< M > | m accepts w" when it accepts w. }. Show T is undecidable.
5. Use Rice's Theorem to prove the undecidablity of the following language. P = {< M...

5. Use Rice's Theorem to prove the undecidablity of the following language. P = {< M > M is a TM and 1011 E L(M)}.
3. Let L= {MM is a Turing machine and L(M) is empty), where L(M) is the...

3. Let L= {MM is a Turing machine and L(M) is empty), where L(M) is the language accepted by M. Prove L is undecidable by finding a reduction from Arm to it, where Arm={<M,w>| M is a Turing machine and M accepts w}

2. Prove that {a"6"c" |m,n0}is not a regular language. Answer: 3. Let L = { M...

2. Prove that {a"6"c" |m,n0}is not a regular language. Answer: 3. Let L = { M M is a Turing machine and L(M) is empty), where L(M) is the language accepted by M. Prove L is undecidable by finding a reduction from Aty to it, where Arm {<M.w>M is a Turing machine and M accepts Answer: 4. a) Define the concept of NP-completeness b) If A is NP-complete, and A has a polynomial time algorithm, then a polynomial time algorithm...
please answer and I will rate! 3. Let L = {M M is a Turing machine...

please answer and I will rate! 3. Let L = {M M is a Turing machine and L(M) is empty), where L(M) is the language accepted by M. Prove Lis undecidable by finding a reduction from Arm to it, where Ayv-<<MwM is a Turing machine and M accepts w). Answer:
Let Show that L is undecidable L = {〈M) IM is a Turing Machine that accepts w whenever it accepts L = {〈M) IM is a Turing Machine that accepts w whenever it accepts

Let Show that L is undecidable L = {〈M) IM is a Turing Machine that accepts w whenever it accepts L = {〈M) IM is a Turing Machine that accepts w whenever it accepts

Use a Turing Reduction to show that the following language is undecidable. L={ | L(M) is...

Use a Turing Reduction to show that the following language is undecidable. L={ | L(M) is infinite}.
8. (15) Let REPEATTM = { <M>M is a TM, and for all s € L(M),...

8. (15) Let REPEATTM = { <M>M is a TM, and for all s € L(M), s = uv where u = v}. Show that REPEATM is undecidable. Do not use Rice's Theorem.
Let S = {a, b}. Show that the language L = {w EX : na(w)<n(w) }...

Let S = {a, b}. Show that the language L = {w EX : na(w)<n(w) } is not regular.

2. Let L = {hMi: M is a Turing machine that accepts at least two binary strings}. a) Define the notions of a recognisabl...

2. Let L = {hMi: M is a Turing machine that accepts at least two binary strings}. a) Define the notions of a recognisable language and an undecidable language. [5 marks] b) Is L Turing-recognisable? Justify your answer with an informal argument. [5 marks] c) Prove that L is undecidable. (Hint: use Rice’s theorem.) [20 marks] d) Bonus: Justify with a formal proof your answer to b). [20 marks] 2. Let L-M M): M is a Turing machine that accepts...