# Questions tagged [rice-theorem]

Rice's Theorem states that any (non-trivial) property of Turing machines is undecidable.

52 questions
Filter by
Sorted by
Tagged with
7k views

### Perplexed by Rice's theorem

Summary: According to Rice's theorem, everything is impossible. And yet, I do this supposedly impossible stuff all the time! Of course, Rice's theorem doesn't simply say "everything is impossible". ...
3k views

### The bounded halting problem is decidable. Why doesn't this conflict with Rice's theorem?

One statement of Rice's theorem is given on page 35 of "Computational Complexity: a Modern Approach" (Arora-Barak): A partial function from $\{0,1\}^*$ to $\{0,1\}^*$ is a function that is not ...
4k views

### What's a trivial property?

I have to show a property P is trivial. This problem has to do with Rice's Theorem, which I do not completely understand. Can someone explain the difference between trivial and non-trivial properties?...
136 views

51 views

### All problems about Turing machines that involve only the language that the TM accepts are undecidable

I came across the below statement in the classic text "Introduction to Automata Theory, Languages, and Computation" by Hopcroft, Ullman, Motwani. ...
866 views

### Using Generalized Rice's Theorem to Prove Decidability

I have a Turing Machine M with a binary alphabet {1,2} that accepts a language L(M) that has infinitely many strings that start with 1 and finitely many strings that start with 2. I'm trying to ...
76 views

### Proving that Rice's theorem does not apply to a property

This is related to an assignment, but I would still appreciate help in formalising proof either through private message or on this topic. The question is about if Rice theorem applies to certain ...
289 views

152 views

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

To my knowledge, lots of languages can be classified as undecidable after applying Rice's theorem, for example {"M" | L(M) is regular}. But what I am not sure is, how to determine if a language is ...
136 views

### Proving that a class of languages is a subset of RE for Rice Theorem

Consider language $L = \{<M> |L(M) \subseteq L(0(0\cup1)^*) \}$ where $<M>$ is a valid encoding of a turing machine. I know that the language is applicable for Rice Theorem. Now, I ...
122 views

### What is the definition of a property?

I have seen 2 answers in stackoverflow: A "trivial" property is one that holds either for all languages or for none. The property is trivial if it contains every TM, or if it is empty. My problem is:...
53 views

### Is the given language decidable?

L = { < M > | M is a turing machine and } Obviously, the language which L(M) is polynomially reducible to, is context free and hence recursive, so it is a decidable language . Now, L(M) is ...
41 views

### Rice's Theorem for Turing machine with fixed output

So I was supposed to prove with the help of Rice's Theorem whether the language: $L_{5} = \{w \in \{0,1\}^{*}|\forall x \in \{0,1\}^{*}, M_{w}(w) =x\}$ is decidable. First of all: I don't understand, ...
216 views

### Trying to prove semidecidability of an undecidable language

I have been having a hard time understanding whether the set $S = \{ M \mid |L(M)| = 5 \}$ is semidecidable or not, where $M$ is a generic Turing Machine and $L(M)$ the language accepted by such TM, ...
278 views

### A question about proving Rice's Theorem by reducing it to the Halting Problem

I've read the definition for Rice's Theorem, here's the one from Wikipedia: In computability theory, Rice's theorem states that all non-trivial, semantic properties of programs are undecidable. ...
47 views

### How can I build a fool proof security system? [closed]

From what I understand, designing an IT security systems requires to build an algorithm D which can decide whether any program M is malicious or not. That tasks looks very similar to me than deciding ...
I need to prove $: L=\left\{<M>| M \text { is a } T M \text { and } L(M)=L\left((01)^{*}\right)\right\} \notin R e$ at first observation it looks like it's immediate from Rice's extended Thm, ...