Register

Can any one proof decidability/undecidability of following on Rice Theorem ?

386 views
0 votes
0 votes

Rice theorem :

1. Any non-trivial property of the LANGUAGE recognizable by a Turing machine is undecidable.

2. Any non-monotonic property of the LANGUAGE recognizable by a Turing machine is unrecognizable

While solving please describe non-trivial/trivial and non-monotonic /monotonic property of particular statement .

Which of the following problems are undecidable?

  1. Membership problem in context-free languages.
  2. Whether a given context-free language is regular.
  3. Whether a finite state automation halts on all inputs.
  4. Membership problem for type 00 languages.
User Avatar

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
1 answer
1
Deepanshu asked Dec 29, 2018
985 views
SELF DOUBT_ RICE THEOREM
L = {<M1, M2>M1 and M2 are two TMs, and ε ∈ L(M1) \ L(M2) }. is it RECURSIVE OR RECURSIVE ENUMERABLE OR NOT EVEN RECURSIVE ENUM.
L = {<M1, M2>M1 and M2 are two TMs, and ε ∈ L(M1) \ L(M2) }.is it RECURSIVE OR RECURSIVE ENUMERABLE OR NOT EVEN RECURSIVE ENUM.
User Avatar
Link Copied!