# Tag Info

Accepted

• 72.8k
Accepted

### What is the definition of a property?

We call a set of languages, $P\subseteq 2^{\Sigma^*}$, a property. If you think of this subset as the set of languages who satisfy some property, then we can simply say that a language $L$ satisfies ...
• 13.5k

### Is the given language decidable?

Yes, your understanding is right. The first part (about context-free languages which are decidable) is unneeded. To apply Rice, you only have to show that the property at hand only depends on $L(M)$ ...
• 14.6k
Accepted

### How to determine enumerability after applying Rice's theorem?

You can use the fact that if $L$ is undecidable and $\overline{L}$ is enumerable then $L$ is not enumerable (since if both $L$ and $\overline{L}$ are enumerable, then $L$ is decidable). In order to ...
• 278k

### Caroll's paradox => Rice theorem?

Well, any true statement implies every other true statement, so in that vacuous sense, I suppose one implies the other. But no, I wouldn't say that Carroll's paradox implies Rice's theorem in any ...
• 164k

### Is the Rice's theorem applicable to $\{ \langle M \rangle \mid M \mbox{ is a Turing machine such that }L(M) = H_{all} \mbox{ } \}$?

Well, Rice's theorem doesn't apply but we don't need it—$L^*$ is empty and therefore decidable. To figure this out, we just need to be meticulous about what these languages are. $L^*$ is the ...
• 778

### Rice's Theorem - usage on $DFA$ or $LBA$

No, you can not. To use Rice, we need to have an "index set", i.e. a set $A$ satisfying $\langle M\rangle\in A \land L(M)=L(N) \implies \langle N\rangle \in A$ for all TMs $M,N$. In other words, the ...
• 14.6k

### Why Rice theorem work for decidability?

Because this process doesn't necessarily end; you can end up discovering more and more possible configurations (state+tape) which would lead to accepting if they were ever reached, but never a legal ...
• 3,192