# Questions tagged [rice-theorem]

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

53 questions
Filter by
Sorted by
Tagged with
31 views

38 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 ...
30 views

138 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 ...
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 ...
298 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 ...
125 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:...
2k views

### Is the Rice Theorem applicable for these problems?

I have 1 problem :--> L = { < M > | TM halts on no inputs } I have solved the above problems by reductions given in the book and even there are many links ...
5k views

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 ...
140 views

### Does Rice theorem imply that it is not possible to find out the absolute optimum of a physical process?

One of my friends works for a big oil rafinery. He's in charge of optimising the inputs (volumes, maximum price to pay for crude oil etc.) given a profit. He's telling me there are heuristic ways to ...
770 views

### Prove whether this problem is decidable or undecidable [duplicate]

So I am reviewing my notes for this problem, and I cant seem to understand how this problem works. Say we have M, and M accepts an input that makes it visit every non-halting state. I convinced ...
360 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 ...
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?