Questions tagged [rice-theorem]

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

Filter by
Sorted by
Tagged with
4
votes
2answers
3k 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 ...
1
vote
1answer
59 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 ...
-1
votes
2answers
147 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 ...
0
votes
1answer
1k 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 ...
-1
votes
1answer
550 views

Use Rice's theorem to prove the following is undecidable

Given the language $L=\{\alpha \mid M_{\alpha}(x)=x^3$ for all $x\in\{0,1\}^*\}$. Prove using Rice's theorem that $L$ is undecidable. Rice's theorem: Let $P$ be a set of all computable functions $f:\...
0
votes
1answer
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?...
2
votes
1answer
279 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
1answer
1k 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 ...
1
vote
2answers
444 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 ...
3
votes
3answers
767 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 ...
4
votes
2answers
5k 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?...
2
votes
1answer
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?
2
votes
1answer
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) \...
44
votes
2answers
8k 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". ...

1
2