# Questions tagged [rice-theorem]

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

70 questions
Filter by
Sorted by
Tagged with
22 views

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 ...
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 vote
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 ...
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
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
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-...
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 ...
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
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
102 views

1 vote
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
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
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
425 views

1 vote
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
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 ...
1 vote
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
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
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, ...
1 vote
885 views

• 113
1 vote
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