# Questions tagged [rice-theorem]

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

77 questions
Filter by
Sorted by
Tagged with
9k 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". ...
5k 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 ...
• 113
1k views

### Prove that "If $L$ is a context-free language, is $\overline{L}$ also context-free?" is undecidable

Lately I need to find the decidability of the following decision problem: If $L$ is a context-free language, is $\overline{L}$ also context-free? I know that context-free language is not closed ...
• 1,132
6k 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?...
4k 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 ...
• 472
197 views

### Deciding whether a Turing machine decides a language $L$ in at most $n^2$ steps

Let $L$ be a language for which there exists some turing machine deciding it in at most $n^2$ steps. Is it decidable whether a given turing machine $M$ decides $L$ and runs in at most $n^2$ steps? I ...
• 223
289 views

• 39
408 views

### Is there a way to tell if ANY machine on ANY input will halt in fewer than n steps OTHER than running the machine for n steps?

Is there a way to tell if ANY machine on ANY input will halt in fewer than n steps OTHER than running the machine for n steps? I've read the similar questions and answers such as here, but I wanted to ...
139 views

1 vote
2k views

### Is L={<M>|M is a TM and L(M) is uncountable} decidable?

Is $L=\{\langle M\rangle\mid \text{$M$is a Turing machine and$L(M)$is uncountable}\}$ decidable? My intuition is that it is not, but I'm not sure if Rice's Theorem applies in this case. If it is ...
1 vote
349 views

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

I have read about Rice's Theorem on Sipser's book, and I think I understand it quite well. I understand that it can be used to show that a language is not decidable. However I am not sure about one ...
• 315
1 vote
499 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 ...
1 vote
47 views

### We cannot recognize a set of languages as the language themselves

"We cannot recognize a set of languages as the language themselves" What is the meaning of the line and why we cannot do it and how is the encoding of TM is helping in that?
1 vote
350 views

### How to determine if this problem is decidable?

I am currently stuck on the following problem: Given a WHILE-program P and the knowledge that all input variales are set to 0, is it decidable if a specific instruction is reached 1000 times? My ...
1 vote
1k views

• 29
1 vote
55 views

### Turing-reducibility for guaranteed decider

The following exercise is taken from Theoretical Computer Science by Atiba. Use Rice's theorem to demonstrate that every decidable language is Turing reducible to some language that is already ...
• 11
1 vote
If $\mathcal{p}$ is a nontrivial property of formal languages, then $L_{\mathcal{p}} = \{ \langle M \rangle \mid L(M) \in \mathcal{p} \}$ is undecidable by Rice’s theorem. What if we describe ...