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

Question

Question

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

Answer 1

Answer #1

L={ | L(M) is infinite}.

The complement of the Halting Problem, denoted by HP(bar), and defined as

HP(bar) = {<M,w>|M is a TM and it does not halt on string w}

HP ̅ (HP bar).ד (<M, x>) = <M’>. M’ on input w:

It runs M on x for |w| steps; it rejects if M halts on x within |w| steps, and accepts otherwise.

We now prove the validity of the reduction:

<M, x>€ HP(bar) ̅ => M does not halt on x =>M accepts all strings => L(M’) is infinite => M’ € L.
< >> not € H P(bar) =>M halts on x within k steps=>M’ rejects all strings whose length is

greater than or equal to k => L(M’) is finite => M’ not € L.

Answer 2

Similar Homework Help Questions

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

(3) Prove that the following language is undecidable L {< M, w> M accepts exactly three strings }. Use a reduction from ArM
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
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}

Show that the language {(M1,M2): M1 and M2 are Turing machines with L(M1) is subset of...

Show that the language {(M1,M2): M1 and M2 are Turing machines with L(M1) is subset of L(M2) is undecidable
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:
2. Let L-M M): M is a Turing machine that accepts at least two binary strings. a) Define the notions of a recognisable...

2. Let L-M M): 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 [5 marks] b) Is L Turing-recognisable? Justify your answer with an informal argument. c) Prove that L is undecidable. (Hint: use Rice's theorem.) [20 marks] 20 marks] d) Bonus: Justify with a formal proof your answer to b). 2. Let L-M M): M is a Turing machine that accepts at...

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...
Help me answer this question plz! 4. Let L = { (A) M is a Turing...

Help me answer this question plz! 4. Let L = { (A) M is a Turing machine that accepts more than one string } a) Define the notions of Turing-recognisable language and undecidable language. b) Is L Turing-recognisable? Justify your answer with an informal argument. c) Justify with a formal proof your answer to b) d) Prove that L is undecidable. (Hint: use Rice's theorem.) e) Modify your answer to b) when instead of L you have the language Ln...
Problem 2. (Undecidable) and prove it (33 points) Formulate the following problem as a language is...

Problem 2. (Undecidable) and prove it (33 points) Formulate the following problem as a language is undecidable Given a Turing machine M determine whether L(M) is context-free Hint: you can reduce the ATM problem to this problem, as we did for the REGULARTM language problem that we discussed in class.

determine if the language is regular, context-free, Turing-decidable, or undecidable. For languages that are regular, give...

determine if the language is regular, context-free, Turing-decidable, or undecidable. For languages that are regular, give a DFA that accepts the language, a regular expression that generates the language, and a maximal list of strings that are pairwise distinguishable with respect to the language. For languages that are context-free but not regular, prove that the language is not regular and either give a context- free grammar that generates the language or a pushdown automaton that accepts the language. You need...