Skip to main content

# Questions tagged [rice-theorem]

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

8 questions
Filter by
Sorted by
Tagged with
46 votes
2 answers
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". ...
5 votes
2 answers
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?...
0 votes
1 answer
2k 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?...
• 149
10 votes
4 answers
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
3 votes
3 answers
857 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 ...
• 703
2 votes
1 answer
316 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 ...
2 votes
1 answer
5k views

### Use Rice's theorem to show that the language of optimisable Turing machines is undecidable

I have an assignment to do and I'm quite stuck with the following question : Use Rice's theorem to show that \$ \qquad L' = \{ \langle M \rangle \mid \; (\exists \text{ TM } M') \; [ L(M') = L(M) \...
• 39
-2 votes
2 answers
211 views

### Why Rice theorem work for decidability?

Rice's theorem states: Every nontrivial property of recursively enumerable language is undecidable. I came across following problems, which Ullman's books say both are undecidable: Turing ...
• 1,677