Skip to main content

Questions tagged [rice-theorem]

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

Filter by
Sorted by
Tagged with
46 votes
2 answers
9k 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". ...
MathematicalOrchid's user avatar
10 votes
4 answers
5k 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 ...
ttbo's user avatar
  • 113
7 votes
1 answer
1k 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 ...
Abhishek Ghosh's user avatar
5 votes
2 answers
6k 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?...
Alex Chumbley's user avatar
5 votes
3 answers
4k 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 ...
Garrick's user avatar
  • 472
4 votes
1 answer
197 views

Deciding whether a Turing machine decides a language $L$ in at most $n^2$ steps

Let $L$ be a language for which there exists some turing machine deciding it in at most $n^2$ steps. Is it decidable whether a given turing machine $M$ decides $L$ and runs in at most $n^2$ steps? I ...
Emolga's user avatar
  • 223
4 votes
1 answer
289 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)\...
pascalhein's user avatar
3 votes
2 answers
3k 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 ...
Ramesh's user avatar
  • 391
3 votes
3 answers
857 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 ...
Hernan_eche's user avatar
3 votes
3 answers
380 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 ...
Keenan Diggs's user avatar
3 votes
1 answer
425 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 ...
Mees de Vries's user avatar
3 votes
1 answer
2k 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 ...
Marc's user avatar
  • 223
2 votes
1 answer
316 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 ...
user2851298's user avatar
2 votes
1 answer
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?
Alvar's user avatar
  • 49
2 votes
2 answers
61 views

Exploiting weaknesses in virus-detecting software?

If a virus is defined as a self-reproducing program, then Rice's theorem implies there can be no infallible virus-detecting algorithm. Can we take that one step further, as follows? If you have the ...
Michael Hardy's user avatar
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'...
Khan Saab's user avatar
  • 253
2 votes
2 answers
3k 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? ...
karalis1's user avatar
  • 131
2 votes
1 answer
5k 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(M) \...
Über Lem's user avatar
2 votes
1 answer
408 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 ...
Garrick White's user avatar
2 votes
1 answer
139 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 ...
sprajagopal's user avatar
2 votes
1 answer
250 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 ...
user127454's user avatar
2 votes
1 answer
407 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$ ...
Xiobiq's user avatar
  • 161
2 votes
1 answer
295 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 ...
Maiaux's user avatar
  • 155
2 votes
1 answer
179 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 ...
user3344312313's user avatar
2 votes
1 answer
248 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 ...
Joseph's user avatar
  • 21
2 votes
1 answer
2k 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 ...
Amal Kahalee's user avatar
2 votes
1 answer
1k 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 ...
Ronit sharma's user avatar
2 votes
1 answer
516 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(...
Gianguido Sorà's user avatar
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 ...
user avatar
1 vote
2 answers
349 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 ...
Alan's user avatar
  • 315
1 vote
2 answers
499 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 ...
Daniel Baughman's user avatar
1 vote
2 answers
47 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?
Sameer Raj's user avatar
1 vote
1 answer
350 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 ...
TheMotivatedGeek's user avatar
1 vote
2 answers
1k 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{ } \}...
blank's user avatar
  • 11
1 vote
2 answers
214 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 ...
Zhao Chen's user avatar
1 vote
1 answer
62 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,...
Vinicius Andrade's user avatar
1 vote
1 answer
240 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 ...
Eloo's user avatar
  • 193
1 vote
1 answer
208 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:...
Stav Alfi's user avatar
  • 125
1 vote
1 answer
63 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 ...
Garrick's user avatar
  • 472
1 vote
2 answers
158 views

Decidability of the minimum number of states a Turing Machine needs to accept a language

I'm reading some old notes from a course on Turing Machines and I've bumped into the following question: Is the following language decidable? The language formed by the set of all Turing Machines ...
user2891462's user avatar
1 vote
1 answer
72 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, ...
Momo's user avatar
  • 35
1 vote
1 answer
114 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. ...
Abhishek Ghosh's user avatar
1 vote
1 answer
507 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, ...
Antonio Frighetto's user avatar
1 vote
1 answer
534 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. ...
doubleOrt's user avatar
  • 113
1 vote
1 answer
67 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 ...
Jerome's user avatar
  • 109
1 vote
0 answers
50 views

How do you use Rice's theorem and why does it make sense? (Use provided Rice's theorem)

So this is the Rice's theorem we were provided: Definition: $TM$-$FUNC(S)$ Input: Turing machine $M$ Question: Is $f_M \in S$ Let $S$ be a set of computable partial functions with $\emptyset \neq S \...
Yuirike's user avatar
  • 29
1 vote
0 answers
55 views

Turing-reducibility for guaranteed decider

The following exercise is taken from Theoretical Computer Science by Atiba. Use Rice's theorem to demonstrate that every decidable language is Turing reducible to some language that is already ...
jase's user avatar
  • 11
1 vote
0 answers
50 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 ...
Omid Yaghoubi's user avatar
1 vote
1 answer
63 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 ...
Florian Bauer's user avatar
1 vote
0 answers
807 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. $...
Abhishek Ghosh's user avatar