Questions tagged [rice-theorem]
Rice's Theorem states that any (non-trivial) property of Turing machines is undecidable.
50
questions
1
vote
1answer
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.
...
1
vote
0answers
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$ => ...
0
votes
1answer
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 ...
0
votes
0answers
24 views
Can you apply Rice's Theorem on the following languages? Are they decidable?
Can you apply Rice's Theorem on the following languages? Are they decidable?
$$L_1:=\{v\mid v \text{ is the Code of a TM } M_v \text{ and } M_v \text{ has an even number of states.}\}$$
$$L_2:=\...
0
votes
1answer
54 views
How can I apply Rice's theorem?
I am learning for my computability and complexity exam in which there is always an exercise to decide whether some problem is decidable or not.
In one of the past exams, there was the following ...
0
votes
0answers
33 views
Use the Rice's theorem to prove that the following property of a Recursive Enumerable language L is undecidable
This exercise was taken from the book "Languages and Machines: An Introduction to the Theory of Computation" by Thomas Sudkamp. It refers to exercise 12 (b) chapter 12. Given a language L which is ...
0
votes
0answers
20 views
Correct Turing machine representation for Rice Theorem proof
Consider the language L1. From Rice Theorem I know L1 is not decidable (i.e. undecidable).
L1 = { R(M) | R(M) is a TM and 1011 ∈ L(M)}
For example if I want to represent by diagram a TM $M_1$ ...
-2
votes
2answers
96 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 ...
2
votes
1answer
71 views
Proving that Rice's theorem does not apply to a property
This is related to an assignment, but I would still appreciate help in formalising proof either through private message or on this topic.
The question is about if Rice theorem applies to certain ...
0
votes
1answer
67 views
Decidability of decision problems
Can somebody give intuition how to answer those questions? From one side I can say that most of them are undecidable because we can reduce the halting problem to them (or halting problem can appear ...
0
votes
1answer
288 views
Rice Theorem - Problem to understand and apply it
I have struggle to understand the Rice Theorem.
My understanding of Rice Theorem:
The purpose of this Theorem is to proof that some given language L is undecidable iff the language has a non-trivial ...
1
vote
1answer
130 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
2answers
115 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 ...
0
votes
2answers
115 views
Can we enumerate finite sequences which have no halting continuation?
Note: this question has been cross-posted to Math.SE, after about a week here.
I am trying to deepen my understanding of the relationship between the Halting Problem and Godel's Completeness Theorem (...
1
vote
1answer
85 views
Rice's theorem applicable to the following language?
Let $L= \{\langle M \rangle \mid M \text{ halts on } \langle M \rangle \} $
be a language where $\langle M \rangle$ is the Code of the TM $M$. $L$ is undecidable.
I've heard that I can't use Rice's ...
1
vote
1answer
441 views
Language of TM is Undecidable
why is this Problem$$L = \{ \langle M\rangle \mid L(M) \text{ is undecidable}\}$$ undecidable?
I thought if we know $L(M)$ the turingmaschine accepts all $x \in L(M)$, so $L(M)$ is in every case ...
2
votes
1answer
593 views
proof of the rice's theorem
Let $P$ be any nontrivial property of the language of a Turing machine. Prove
that the problem of determining whether a given TM’s language has property $P$ is undecidable.
Proof:(This is from sipser'...
3
votes
3answers
360 views
What is the Name of the Problem or Technique of Determining if a Line in a Program Will Execute
If I were to pose the question: "Given a program $P$ containing statement $X$, will $X$ be executed (given enough runs with all possible inputs)?"
This strikes me of being a relative of the Halting ...
1
vote
1answer
194 views
Trying to prove semidecidability of an undecidable language
I have been having a hard time understanding whether the set $S = \{ M \mid |L(M)| = 5 \}$ is semidecidable or not, where $M$ is a generic Turing Machine and $L(M)$ the language accepted by such TM, ...
2
votes
1answer
268 views
Rice's theorem application on a language that resembles ETM
I'm working on an exercise that involves checking if the Rice's theorem can be applied on a two languages.
The first language is $E_{TM} = \{ \langle M \rangle \text{ | M is a Turing Machine and } L(...
1
vote
1answer
270 views
A question about proving Rice's Theorem by reducing it to the Halting Problem
I've read the definition for Rice's Theorem, here's the one from Wikipedia:
In computability theory, Rice's theorem states that all non-trivial,
semantic properties of programs are undecidable. ...
0
votes
1answer
1k 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
1answer
45 views
How can I build a fool proof security system? [closed]
From what I understand, designing an IT security systems requires to build an algorithm D which can decide whether any program M is malicious or not.
That tasks looks very similar to me than deciding ...
0
votes
1answer
51 views
Caroll's paradox => Rice theorem?
To me (but I might be wrong) Rice's theorem asserts that it's not possible to formalise the demonstration of a non-trivial property of a recursively enumerable language within the same given language. ...
-2
votes
1answer
35 views
Show that $L = L_\phi \cup L_{\{\sum^*\}} \notin RE$ with Rice theorem
Show that $L = L_\phi \cup L_{\{\sum^*\}} \notin RE$ with Rice theorem.
Well I did show that with reduction, by using $HP'$.
Simply by creating a function from $f(\langle M \rangle, x) = (M')$
Thus,...
1
vote
2answers
393 views
Is the Rice's theorem applicable to $\{ \langle M \rangle \mid M \mbox{ is a Turing machine such that }L(M) = H_{all} \mbox{ } \}$?
Until just now I thought that I have fully understood Rice's theorem but this example irritates me:
$L^* = \{ \langle M \rangle \mid M \mbox{ is a Turing machine such that }L(M) = H_{all} \mbox{ } \}...
3
votes
2answers
2k views
Why is “accepted by Turing Machine with even number of states” a trivial property?
$$
L = \left\{ \left< M \right>~\middle|~
\small{
\begin{array}{l}
L(M)\text{ is recognized by a Turing Machine} \\
\text{having even number of states}
\end{array}
}
\right\}.
$$
Isn't $L$ same ...
1
vote
1answer
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 ...
9
votes
4answers
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 ...
1
vote
1answer
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:...
0
votes
0answers
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-...
3
votes
1answer
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
...
0
votes
0answers
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 ...
0
votes
2answers
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 ...
1
vote
2answers
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 ...
4
votes
1answer
130 views
Decide the set of all Turing machines with $L(M)=\left\{\langle M\rangle\right\}$
How can I prove that the language $L=\left\{\langle M\rangle\mid L(M)=\left\{\langle M\rangle\right\}\right\}$ is not decidable?
When trying to use a diagonal argument, I cannot conclude from $L(M)\...
4
votes
2answers
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 ...
1
vote
1answer
52 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
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 ...
0
votes
1answer
721 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
518 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
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 ...
2
votes
1answer
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 ...
1
vote
2answers
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 ...
3
votes
3answers
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 ...
4
votes
2answers
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?...
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
4k 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(...
38
votes
2answers
7k 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". ...
