# Tag Info

## Hot answers tagged rice-theorem

Accepted

### Why is "accepted by Turing Machine with even number of states" a trivial property?

All recognisable languages are recognised by a TM with an even number of states, so the property is trivial. If a language is recognisable, there is (by definition) a TM that recognises it. If it ...
• 17.8k
Accepted

• 71.2k

### 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 ...
• 145k
### 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 ...
### 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 ...