Recent questions tagged rice-theorem

0 votes
1 answer
5
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.
1 votes
0 answers
13
11 votes
2 answers
21
My Question $\{\langle M \rangle \mid M$ is a TM and there exist an input whose length is less than 100, on which $M$ halts$\}$I have to check that it is Turing Recogniza...
0 votes
0 answers
24
0 votes
0 answers
25
L(M)has at most 10 stringsWe can have Tyesfor ϕ and Tno for Σ∗. Hence, L={M∣L(M) has at most 10 strings} is not Turing decidable (not recursive). problem :It should...
5 votes
1 answer
28
I am unable to understand when to apply Rice's theorem and when to not. How L2 is decidable.
1 votes
1 answer
29
I mean how it is a trivial property, we can write Tyes ( TM having even states) and Tno ( TM having odd states) for it.Can Turing machine can never have odd number of sta...