15
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 ...
- 18.3k
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 ...
- 72.9k
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 ...
- 3,192
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,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 ...
- 82.2k
7
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,516
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 ...
- 219
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.7k
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 ...
- 788
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.6k
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 ...
- 402
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 ...
- 315
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 ...
- 352
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 ...
- 39.1k
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,547
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.7k
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
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 ...
- 82.2k
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:
...
- 336
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 ...
- 279k
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.7k
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.6k
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 ...
- 72.9k
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.♦
- 166k
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 ...
- 778
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.7k
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 ...
- 3,192
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.♦
- 166k
2
votes
Is there a connection between the Undecidability Theorem and "software complexity"?
The author is here referring to the Halting problem, and possibly also Rice's theorem (without putting words into their mouths).
It says indeed that it's not possible to decide in advance whether a ...
- 17.1k
2
votes
Accepted
Is this a correct application of Rice-Shapiro theorem?
The application of the theorem is not correct. Note that $\mathcal{L}$ is a set of acceptable languages, and consider your first point. If you take an acceptable language $L$ that contains a string of ...
- 4,874
Only top scored, non community-wiki answers of a minimum length are eligible