Questions tagged [rice-theorem]
Rice's Theorem states that any (non-trivial) property of Turing machines is undecidable.
70
questions
0
votes
1
answer
22
views
Reductions but no algorithms
in "Introduction to Automata Theory, Languages and Computations" by Motwani, Ullman and Hopcroft, when they need to prove, for instance, Rice's theorem, they reduce the universal language, $...
- 1
2
votes
1
answer
64
views
Showing that a property is semantic - Rice's theorem
I want to show that the language
$$L= \left\{ \left\langle M\right\rangle \mid\substack{\text{M is a TM and there exists a poly TM $M'$ such that}\\
\text{if M halts on input $w$, $M'$ halts on $w$ ...
- 161
1
vote
0
answers
37
views
Does description method matter in Rice’s theorem?
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 ...
- 358
1
vote
2
answers
39
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?
- 11
2
votes
2
answers
430
views
Why is a Language L(M) {has at least 10 strings} turing recognizable and L(N) {has at most 10 strings} is not?
Why is a Language L(M) {has at least 10 strings} recognizable and L(N) {has at most 10 strings} is not?
...
- 131
0
votes
0
answers
32
views
Undecidability of a set of Turing Machines
Considering the following set, I have to say if it is undecidable, decidable or semidecidable:
$$S_1 = \{y | \forall n \text{ the Turing Machine } M_y \text{ does not accept any string of length } n\}$...
2
votes
1
answer
121
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 ...
0
votes
1
answer
125
views
Rice theorem could apply except RE language?
You know that Rice theorem is applicable to check decidability of RE language. Also we know that all regular, deterministic context free, context free, recursive languages are RE languages.
$Q_1:$ So ...
- 1
1
vote
1
answer
68
views
Could I apply Rice theorem for both TM's property and language property?
I read that Rice theorem applicable only for language property not for machine property. But today I have read from stack exchange and one site they are applying Rice theorem on machine also. My ...
- 1
7
votes
1
answer
398
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,032
0
votes
0
answers
34
views
Is this language in RE?
Given the following language:
$$L=\left \{ <M> | \exists L \in R \quad s.t \quad L(M)\subseteq L \right \}$$
I need to determine it's compuation class(R or RE).
I used Rice Theorem as follows to ...
- 219
0
votes
1
answer
71
views
Can a TM decide the binary PCP-Problem？
I am having a little bit of a hard time distinguish between a TM which accepts a language, and a $TM$ that decides a language. To be more precise:
$L_1 = \{\langle M\rangle\; | \; M$ accepts the 10-...
- 1
0
votes
1
answer
103
views
A question on decidability
I have a homework question that is as follows:
L(P) is a language of ASCII input strings for which a given program, P, returns "yes". Is the set of all input strings P decidable, such that P ...
- 3
0
votes
0
answers
31
views
Is my assumption about non trivial propery correct?
"make sure you understand why for a non trivial property $S$, $\bar{S}$ is also non trivial"
My assumption is: $S$ is non trivial property: There are L1,L2 such that $L_{1},L_{2}\in RE$ and ...
- 219
0
votes
1
answer
106
views
Using Rice's theorem to prove undecidability of $E_{TM}$
I saw this proof and I wondered if I could prove $E_{TM}$ with Rice's theorem similar to the one described in the answer. Can you do the same thing by letting $M$ to only accept empty strings? (the $M$...
- 343
2
votes
1
answer
102
views
Is this a correct application of Rice-Shapiro theorem?
Let $\langle M\rangle$ be the encoding of a Turing machine as a string over $\Sigma=\{0,1\}$, and consider the language $L=\{\langle M\rangle| \text{ $M$ is a Turing machine that accepts a string of ...
- 229
1
vote
1
answer
50
views
Is there a connection between the Undecidability Theorem and "software complexity"?
I was reading Complexity: The Emerging Science at the Edge of Order and
Chaos and a certain passage got me really intrigued. When discussing
Chris Langton's explorations of artificial life algorithms,...
2
votes
1
answer
109
views
Halting (on empty input tape) for an infinite subset of all Turing machines
As is well known, there is no single procedure for deciding whether any given Turing machine halts on an empty input tape. This is easily shown, e. g., by applying Rice's theorem.
But what if, instead ...
- 155
0
votes
1
answer
600
views
Determine if a language is Decidable or semi decidable
Consider the language $L = \{\langle M \rangle: \text{ $M$ accepts at most two single-letter words}\}$, where $\langle M\rangle$ is the encoding of Turing machine $M$.
We need to determine, without ...
- 13
1
vote
1
answer
126
views
Is Rice's Theorem equivalent to the Halting problem?
As I understand it Rice's Theorem seems to imply the existence of the Halting problem. That is, with Rice's Theorem, we can prove that the Halting problem is undecidable. However, to me, it seems like ...
- 13
1
vote
1
answer
44
views
Why is the following language undecidable?
I'm currently learning for my exams this semester and tried to solve some old exams from the last years.
The question is to show, that L ist undecidable.
$L=\{w|T(M_w)\neq\emptyset \land \forall x \in ...
1
vote
1
answer
67
views
Rice's Theorem for Turing machine with fixed output
So I was supposed to prove with the help of Rice's Theorem whether the language:
$L_{5} = \{w \in \{0,1\}^{*}|\forall x \in \{0,1\}^{*}, M_{w}(w) =x\}$ is decidable.
First of all: I don't understand, ...
- 35
2
votes
1
answer
117
views
Prove the language of Turing machines that recognize (01)^* is not recursive
I need to prove
$: L=\left\{\langle M\rangle\mid M \text { is a } T M \text { and } L(M)=L\left((01)^{*}\right)\right\} \notin Re$
at first observation it looks like it's immediate from Rice's ...
1
vote
1
answer
78
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,032
1
vote
0
answers
425
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.
$...
- 1,032
0
votes
1
answer
68
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 ...
- 51
0
votes
1
answer
194
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 ...
- 199
-2
votes
2
answers
188
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,557
2
votes
1
answer
189
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 ...
- 21
0
votes
1
answer
209
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 ...
- 3
0
votes
1
answer
2k
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
1
answer
244
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
2
answers
275
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
0
votes
3
answers
160
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 (...
- 115
1
vote
1
answer
118
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 ...
- 113
3
votes
1
answer
1k
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 ...
- 113
2
votes
1
answer
1k
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'...
- 253
3
votes
3
answers
370
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 ...
- 133
1
vote
1
answer
412
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
1
answer
427
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
1
answer
463
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. ...
- 113
1
vote
1
answer
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 ...
user87413
1
vote
1
answer
63
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 ...
- 109
-1
votes
1
answer
71
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. ...
- 109
-2
votes
1
answer
46
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, ...
- 203
1
vote
2
answers
885
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{ } \}...
- 11
3
votes
2
answers
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 ...
- 381
1
vote
1
answer
214
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 ...
- 93
10
votes
4
answers
4k
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
1
vote
1
answer
185
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:...
- 125