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 ...
Luke Mathieson's user avatar
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 ...
Raphael's user avatar
  • 72.4k
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 ...
Alexey Romanov's user avatar
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 ...
Curtis F's user avatar
  • 1,043
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 ...
David Richerby's user avatar
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 ...
Jirka Hanika's user avatar
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, ...
chi's user avatar
  • 14.6k
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 ...
Hans Hüttel's user avatar
  • 2,496
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 ...
Ariel's user avatar
  • 13.4k
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 ...
Christopher King's user avatar
5 votes
Accepted

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

This problem is indeed undecidable, assuming that $n$ is not a constant but refers to the length of the machine's input. Consider the problem $P$ of, given a Turing machine $\mathcal{M}$, to decide if ...
Rémi's user avatar
  • 402
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 ...
John L.'s user avatar
  • 39k
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 ...
exfret's user avatar
  • 342
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 ...
MysticForce's user avatar
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 ...
Joey Eremondi's user avatar
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 ...
Mark Dominus's user avatar
  • 1,537
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....
Raphael's user avatar
  • 72.4k
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 ...
David Richerby's user avatar
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 ...
Vor's user avatar
  • 12.5k
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 ...
3 votes

Exploiting weaknesses in virus-detecting software?

Following the reasoning of the Halting Problem, you can indeed make a "virus" that performs the following action: ...
Сергей Макеев's user avatar
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 ...
Raphael's user avatar
  • 72.4k
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 ...
Ariel's user avatar
  • 13.4k
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 ...
Yuval Filmus's user avatar
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)$ ...
chi's user avatar
  • 14.6k
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 ...
D.W.'s user avatar
  • 159k
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 ...
user326210's user avatar
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 ...
chi's user avatar
  • 14.6k
2 votes

Why Rice theorem work for decidability?

Because this process doesn't necessarily end; you can end up discovering more and more possible configurations (state+tape) which would lead to accepting if they were ever reached, but never a legal ...
Alexey Romanov's user avatar
2 votes
Accepted

Is Rice's Theorem equivalent to the Halting problem?

Yes, you can prove Rice's theorem by reduction from the Halting problem. See https://en.wikipedia.org/wiki/Rice%27s_theorem#Proof_by_reduction_from_the_halting_problem. The reverse direction is also ...
D.W.'s user avatar
  • 159k

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