Questions tagged [rice-theorem]

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

Filter by
Sorted by
Tagged with
0
votes
1answer
77 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
vote
1answer
37 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 ...
4
votes
0answers
66 views

How to prove that the problem $\text{"If $L$ is a context-free language, then, is $\overline{L}$ also context-free?"}$ is undecidable?

Lately I came across a problem: $\text{"If $L$ is a context-free language, then, is $\overline{L}$ also context-free?"}$ And I need to comment on its decidability. Now I know that context free ...
0
votes
0answers
28 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 ...
0
votes
1answer
41 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 = \{<M> \; | \; M$ accepts the 10-PCP $\}...
0
votes
1answer
90 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 ...
0
votes
0answers
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 ...
0
votes
1answer
49 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$...
2
votes
1answer
78 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 ...
1
vote
1answer
42 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
1answer
49 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 ...
0
votes
1answer
355 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 ...
0
votes
0answers
22 views

Modern vs. original formulations of Rice's theorem

Rice's theorem states that any nontrivial semantic property of Turing machines is undecidable. However, when I opened “Classes of recursively enumerable sets and their decision problems” by H. G. Rice,...
1
vote
1answer
67 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 ...
1
vote
1answer
37 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
1answer
57 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, ...
2
votes
1answer
60 views

Prove a language is not recursive enumerable

I need to prove $: L=\left\{<M>| M \text { is a } T M \text { and } L(M)=L\left((01)^{*}\right)\right\} \notin R e$ at first observation it looks like it's immediate from Rice's extended Thm, ...
1
vote
1answer
66 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
198 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. $...
0
votes
1answer
57 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
1answer
136 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 ...
-2
votes
2answers
167 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
150 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
147 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
1k 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
196 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
221 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
134 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
106 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
815 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
833 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
364 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
322 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
366 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
397 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. ...
1
vote
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
53 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
61 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
38 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
679 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
190 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 ...
10
votes
4answers
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 ...
1
vote
1answer
162 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
56 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
360 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
54 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
2k 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
182 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
194 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)\...