14 votes
Accepted

Why is "accepted by Turing Machine with even number of states" a trivial property?

All recognisable languages are recognised by a TM with an even number of states, so the property is trivial. If a language is recognisable, there is (by definition) a TM that recognises it. If it ...
14 votes
Accepted

The bounded halting problem is decidable. Why doesn't this conflict with Rice's theorem?

The language $\qquad \{(α,x,n):M_α \text{ accepts } x \text{ in less than } n \text{ steps}\}$ is not an index set, that is it is not of the form $\qquad L_P = \{ \langle M \rangle \mid M \text{ is ...
  • 71.2k
10 votes

Is L={<M>|M is a TM and L(M) is uncountable} decidable?

This is somewhat of a trick question. What you are missing is that there are no uncountable languages over a finite (or even countable) alphabet. This should be enough information to answer it. (I ...
8 votes
Accepted

What is the Name of the Problem or Technique of Determining if a Line in a Program Will Execute

This is called the reachability problem -- is it possible for a given system to enter a given state? Techniques that attempt to answer this problem fall under reachability analysis, which is one of ...
  • 1,003
7 votes

Why is "accepted by Turing Machine with even number of states" a trivial property?

In the context of Rice's theorem, a class of languages is trivial if either it contains all RE languages; it contains no RE languages. In your case, the language is trivial for the first reason, as ...
7 votes
Accepted

What is the meaning of undecidability in Rice Theorem?

Undecidable means not decidable. Undecidable problems may or may not be semi-decidable. To see that an undecidable problem is not necessarily semi-decidable, observe that there are uncountably many ...
6 votes

RICE theorem applications

The major hypothesis of Rice theorem is that you are dealing with a set which is "extensional", or "semantically closed". Formally this requires that when the encoding of a TM $M$ belongs to the set, ...
  • 14.2k
6 votes

The bounded halting problem is decidable. Why doesn't this conflict with Rice's theorem?

The Rice theorem says that you can't tell anything about the ultimate behavior of a program when it is left to run to infinity - no matter how you classify programs, there will be two programs that ...
5 votes

What is the Name of the Problem or Technique of Determining if a Line in a Program Will Execute

EDIT: This answer is more detailed than mine. This is an example of a question covered by Rice's theorem. For example, the question of if a program outputs "Hello World" or not is covered by that ...
  • 766
5 votes

Is the Rice Theorem applicable for these problems?

Rice's theorem cannot be used to show the undecidability of these two languages. Most of the incorrect attempts that I have come across, are based on the misunderstanding that the notion of property ...
  • 2,446
5 votes
Accepted

Rice's Theorem: implication of having an undecidable property

An undecidable property $\pi$ of Turing machines is the same as an undecidable language consisting of all encodings of Turing machines satisfying $\pi$. We identify the property with the language of ...
5 votes

The bounded halting problem is decidable. Why doesn't this conflict with Rice's theorem?

First, the words in your language aren't encodings of machines, they contain more information, so you can't directly apply Rice theorem. That said, Rice's theorem talks about the impossibility of ...
  • 13.2k
4 votes
Accepted

Decide the set of all Turing machines with $L(M)=\left\{\langle M\rangle\right\}$

The recursion theorem states that a Turing machine can get its own description on to its tape. In fact, there is a simple reduction from the acceptance problem (ATM) to this problem. Assume $L$ is ...
4 votes
Accepted

Rice's Theorem for Total Computable Functions

Almost The correct answer is that a property of recursive languages is r.e. if and only if it can be verified by a finite number of values (though unlike in your example the exact number of values ...
  • 332
4 votes

What's a trivial property?

A "property" is simply a subset of languages in $RE$ -- the set of all the languages that "satisfy" that property. A non-trivial property $P$ is a non-empty set $P$ which is strictly contained in $RE$,...
  • 20.4k
4 votes

Does Rice theorem imply that it is not possible to find out the absolute optimum of a physical process?

Rice's theorem states that you can't decide a non-trivial property of Turing Machines in general. You are asking, "given a specific Turing Machine, can I find some property about it." The answer is ...
  • 29.2k
4 votes
Accepted

proof of the rice's theorem

Let us verify that $S$ is a decider for $A_{\text{TM}} = \{⟨M,w⟩\mid M \text{ is a TM and }M\text{ accepts } w\}$. Let $⟨M,w⟩\in A_{\text{TM}}$ be the input to $S$. Let us see how $S$ runs according ...
  • 35.5k
4 votes

Why Rice theorem work for decidability?

You said in a comment: I am talking to process this encoding, not the tape content. But the tape content affects the behavior of the TM, including whether it would enter an accepting state. The ...
  • 1,517
3 votes

The bounded halting problem is decidable. Why doesn't this conflict with Rice's theorem?

Rice's theorem says that, for any nontrivial set $\mathcal{L}$ of languages, the set of Turing machines that recognize a language in $\mathcal{L}$ is undecidable. Wikipedia says that a specific ...
3 votes

Does Rice theorem imply that it is not possible to find out the absolute optimum of a physical process?

You are estimating that processes at an oil refinery are computable -- that may very well be true. However, it's unlikely that they are Turing-complete. Unless they are, Rice's theorem does not apply....
  • 71.2k
3 votes
Accepted

Rice's Theorem - usage on $DFA$ or $LBA$

If when you say "$M$ is a $LBA$ (or $DFA$ or $PDA$)" you mean that $M$ has a fixed decidable structure (i.e. some properties of its internal state/transition structure) that forces its behaviour to ...
  • 12.3k
3 votes

How to determine if this problem is decidable?

As Konstantin Vladimirov said in the comment: Consider you have this program. Take any while-program and put any instruction 1000 times just before halt. Next run your program and ask if this ...
2 votes

Is the given language decidable?

Yes, your understanding is right. The first part (about context-free languages which are decidable) is unneeded. To apply Rice, you only have to show that the property at hand only depends on $L(M)$ ...
  • 14.2k
2 votes

Prove Undecidability: TM M enters each of its states on Input W?

Hint. We can assume that a Turing machine has exactly one halting state. If a TM visits all of its states, it certainly visits the halting state. Now figure out a way to modify Turing machines so that,...
2 votes
Accepted

What is the definition of a property?

We call a set of languages, $P\subseteq 2^{\Sigma^*}$, a property. If you think of this subset as the set of languages who satisfy some property, then we can simply say that a language $L$ satisfies ...
  • 13.2k
2 votes
Accepted

How to determine enumerability after applying Rice's theorem?

You can use the fact that if $L$ is undecidable and $\overline{L}$ is enumerable then $L$ is not enumerable (since if both $L$ and $\overline{L}$ are enumerable, then $L$ is decidable). In order to ...
2 votes
Accepted

Proving that a class of languages is a subset of RE for Rice Theorem

You missed a tiny detail when defining $C$: all those languages are RE by assumption; no other language can be an $L(M)$! Let us again look at the language you want to say something about: $\qquad ...
  • 71.2k
2 votes

Caroll's paradox => Rice theorem?

Well, any true statement implies every other true statement, so in that vacuous sense, I suppose one implies the other. But no, I wouldn't say that Carroll's paradox implies Rice's theorem in any ...
  • 145k
2 votes

Is the Rice's theorem applicable to $\{ \langle M \rangle \mid M \mbox{ is a Turing machine such that }L(M) = H_{all} \mbox{ } \}$?

Well, Rice's theorem doesn't apply but we don't need it—$L^*$ is empty and therefore decidable. To figure this out, we just need to be meticulous about what these languages are. $L^*$ is the ...
2 votes

Rice's Theorem - usage on $DFA$ or $LBA$

No, you can not. To use Rice, we need to have an "index set", i.e. a set $A$ satisfying $\langle M\rangle\in A \land L(M)=L(N) \implies \langle N\rangle \in A$ for all TMs $M,N$. In other words, the ...
  • 14.2k

Only top scored, non community-wiki answers of a minimum length are eligible