Explain proof of rice-s theorem for infinite language

Assignment Help Theory of Computation

Reference no: EM1388005

Let the following transformation f which maps each pair <M,w> consisting of Turing machine M and input w to M to another Turing machine M ,w N? ?. TM M ,w N? ? when given input string x over its input alphabet Σ behaves as follows. M ,w N? ? simulates computation of M on w for |x| steps (where |x| is the length of x). If M doesn't accept within these steps, then M ,w N? ? accepts its own input x and halts. If M accepts during steps, then M ,w N? ? rejects its input x and halts.
1. Assume that M accepts w. What is L( M ,w N? ? )?
2. Assume that M doesn't accept w. What is L( M ,w N? ? )?
3. Use the transformation f to show that language { <N> | N is Turing machine whose language L(N) is infinite } is not recursively enumerable.
4. If you perform reduction in proof of Rice's theorem for special case of property P: "infinite language", does this reduction also show that language P L = { <N> | N is Turing machine whose language L(N) is infinite } is not recursively enumerable? Describe why it does or it doesn't.

Reference no: EM1388005

Questions Cloud

Should be equal between hcns and expatriates in equivalent : If you were a host-country national (HCN), would you think salaries should be equal between HCNs and expatriates in equivalent positions, even though the cost of living is lower in the host country?

Ethical ramifications of removing pacemaker : You're David Jamison, MHA, ethics committee chairman at Marion General Hospital. Coming before your committee today is the case of Margie Whitson, age 95, who wishes to have her pacemaker deactivated.

Bioethics in laymans terms : What is medical law, ethics, and bioethics in laymans terms (not dictionary)? Critically discuss the importance of each of these in the medical environment?

Describe in detail how the ethical culture of goodwill : Describe in detail how the ethical culture of Goodwill of San Franciso contributes to its organizational strategy.

Explain proof of rice-s theorem for infinite language : If you perform reduction in proof of Rice's theorem for special case of property P: "infinite language", does this reduction also show that language P L = { | N is Turing machine.

Intentional or quasi intentional tort : Critically discuss and detail a recent case involving an intentional or quasi intentional tort in health care. What are the ethical considerations and ramifications of this case?

Explain how pepsi cola benefits from being socially : explain how Pepsi cola benefits from being socially responsible, either financially or in some other way. Explain how you think Pepsi cola might be harmed

Probability that exactly one woman is selected : Satellite Office Systems has vacancies for two executives that it will fill from among four women and six men. What is the probability that exactly one woman is selected?

Respond to the colleague concern : Describe in practical language how you would respond to the colleague's concern that the qualitative research report findings in your research support base do not include "hard data".

User Account

All Pages