# Questions tagged [rice-theorem]

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

50 questions
Filter by
Sorted by
Tagged with
36 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. ...
25 views

### Rice theorem, the proof of the part when the empty language belongs to the property

I was going through the classic text "Introduction to Automata Theory, Languages, and Computation" by Hofcroft, Ullman and Motwani where I came across the proof the Rice theorem as shown. $L_u$ => ...
25 views

### EVEN-CFL Decidable / Undecidable - Rice-Theorem

Let EVEN-CFL $=\left\{w | M_{w} \text { is a } \mathrm{TM}, \text { such that } L\left(M_{w} \right) \\ \text{ has only words with even length and is context free.}\right .\}$ Question : Is EVEN-CFL ...
24 views

128 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 ...
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 ...
118 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:...
54 views

### Is undecidability of TMs' properties a statistical statement?

We know (by Rice's theorem) that is it not possible to decide a non-trivial property of a given TM. We could say therefore that we cannot be sure at 100 percent that a given TM has a certain non-...
291 views

### Rice's Theorem for Total Computable Functions

Fix a Gödel numbering, and write $\phi_n$ for the function coded by $n$. Rice's theorem states that if $P$ is the set of partial computable functions, and $A \subseteq P$, then the decision problem ...
46 views

### Reduction without Rice's Theorem

How can I show that the following language is neither semi decidable nor co-semi decidable without using Rice's Theorem? Further for the following language, how would I show that it IS co-semi ...
1k views

### RICE theorem applications

I am having some confusion in understanding RICE's theorem. It says every non trivial property of RE in undecidable. I need to understand when to apply RICE's theorem and when to not. Questions ...
148 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 ...
130 views

1k views

### Prove Undecidability: TM M enters each of its states on Input W?

Consider the following problem: given a Turing Machine $M$ and an input string $w$, does $M$ enter each of its states during its computation on input $w$? How to prove that the problem is undecidable?...
236 views

### What is the meaning of undecidability in Rice Theorem?

Rice theorem says every non-trivial property of languages of Turing machines is undecidable. what is the meaning of undecidability here? is it semi-decidable? As an example the following language is ...
827 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 ...
355 views

### Rice's Theorem: implication of having an undecidable property

I understand the assumptions that have to be true about a property or set of properties in a Turing machine description for Rice's Theorem to apply. But then what? If a set of Turing machines have ...
745 views

### Rice's theorem vs Turing completeness

I would like to clarify this because I see some kind of contradiction between Rice's theorem and Turing completeness. This is the problem: In building an Universal Turing Machine to emulate another ...
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?...
6k views

### Rice Theorem - What is non-trivial property? [duplicate]

Every nontrivial property of the recursively enumerable languages is undecidable. What exactly is nontrivial property?