Questions tagged [rice-theorem]
Rice's Theorem states that any (non-trivial) property of Turing machines is undecidable.
45
questions
0
votes
0answers
15 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
77 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
vote
1answer
51 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
48 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
116 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
100 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
78 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
0answers
105 views
How to show that the complement of ATM $\leq_{m}$ L = {<M> : |L(M)| = 2}?
My original intention was to prove that $L = \{\langle M \rangle \mid |L(M)| = 2 \}$ is not turing recognizable but soon I realized that I could use the complement of ATM because the complement of ...
0
votes
2answers
105 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
74 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
298 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
390 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
356 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
137 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
210 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
212 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
43 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
49 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
34 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
305 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
1k 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
115 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
95 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
53 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-...
2
votes
1answer
245 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
44 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
140 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
111 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
49 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
138 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
605 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
494 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
965 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
212 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
736 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
332 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
727 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?...
1
vote
1answer
5k 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(...
37
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". ...
