patternMinor
Is the Rice Theorem applicable for these problems?
Viewed 0 times
thethesefortheoremapplicableproblemsrice
Problem
I have 1 problem :-->
I have solved the above problems by reductions given in the book and even there are many links in stackexchange site. I have no problems in the reduction method.
But, just trying to be more curious, I tried to solved these problems by using rice theorem. I know that rice theorem is applied on the property of languages and here it is property of TM's but i tried some conversion here .
Though, I am getting the right answer but i want to confirm is what i have tried is legal or Can It be solved like this ?
As the TM halts on no inputs, which means it is not halting on the inputs in the language as well as inputs not in the language.
which is surely a non trivial property and as well as non monotonic property, hence the language is Undecidable and as well as Non RE.
Well, I am new to this topic. So, i don't know whether I am right in the conversions or Can I assume something like this. Please correct me if i am being stupid .
L = { | TM halts on no inputs }I have solved the above problems by reductions given in the book and even there are many links in stackexchange site. I have no problems in the reduction method.
But, just trying to be more curious, I tried to solved these problems by using rice theorem. I know that rice theorem is applied on the property of languages and here it is property of TM's but i tried some conversion here .
Though, I am getting the right answer but i want to confirm is what i have tried is legal or Can It be solved like this ?
As the TM halts on no inputs, which means it is not halting on the inputs in the language as well as inputs not in the language.
So, I wrote it as
L = { | L(M) = PHI }which is surely a non trivial property and as well as non monotonic property, hence the language is Undecidable and as well as Non RE.
Well, I am new to this topic. So, i don't know whether I am right in the conversions or Can I assume something like this. Please correct me if i am being stupid .
Solution
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 is a vague notion from everyday life. However, a property means something very precise in the context of computability theory: A property is a class of Turing-recognizable languages.
Rice's theorem can be applied whenever we are faced with a non-trivial class of Turing-recognizable languages $\mathcal{S}$, that is, a class of Turing-recognizable languages that is neither the empty class or the class of all Turing-recognizable languages. Rice's theorem tells us that if $\mathcal{S}$ is a non-trivial class of Turing-recognizable languages, then
$$L_{\mathcal{S}} = \{ \langle M \rangle \mid M \text{ is a Turing machine such that } L(M) \in \mathcal{S} \}$$
is undecidable.
But there is no class of recognizable languages that corresponds to
$$A = \{ \langle M \rangle \mid M \text{ halts on no input} \}$$
For consider the Turing machines $M_1$:
"On input $x$, loop forever"
and $M_2$:
"On input $x$, reject"
We have that $\langle M_1 \rangle \in A$ but $\langle M_2 \rangle \notin A$, while we also have $L(M_1) = L(M_2)$.
Similarly, there is no class of languages that corresponds to
$$B = \{ \langle M \rangle \mid M \text{ halts on at least one input} \}$$
Here, we can choose $M_1$ as
$M_1:$ "On input $x$, if $x = aa$ then reject, else loop forever"
and $M_2$ as
$M_1:$ "On input $x$, reject"
Again we have that $\langle M_1 \rangle \in A$ but $\langle M_2 \rangle \notin A$, while we also have $L(M_1) = L(M_2)$.
A correct application of Rice's theorem to a decision problem about Turing machines must identify a non-trivial class of Turing-recognizable languages that the decision problem corresponds to.
See my note http://people.cs.aau.dk/~hans/ANoteOnRicesTheorem.pdf for more about correct applications of Rice's theorem as well as a discussion of incorrect applications of the theorem.
Most of the incorrect attempts that I have come across, are based on the misunderstanding that the notion of property is a vague notion from everyday life. However, a property means something very precise in the context of computability theory: A property is a class of Turing-recognizable languages.
Rice's theorem can be applied whenever we are faced with a non-trivial class of Turing-recognizable languages $\mathcal{S}$, that is, a class of Turing-recognizable languages that is neither the empty class or the class of all Turing-recognizable languages. Rice's theorem tells us that if $\mathcal{S}$ is a non-trivial class of Turing-recognizable languages, then
$$L_{\mathcal{S}} = \{ \langle M \rangle \mid M \text{ is a Turing machine such that } L(M) \in \mathcal{S} \}$$
is undecidable.
But there is no class of recognizable languages that corresponds to
$$A = \{ \langle M \rangle \mid M \text{ halts on no input} \}$$
For consider the Turing machines $M_1$:
"On input $x$, loop forever"
and $M_2$:
"On input $x$, reject"
We have that $\langle M_1 \rangle \in A$ but $\langle M_2 \rangle \notin A$, while we also have $L(M_1) = L(M_2)$.
Similarly, there is no class of languages that corresponds to
$$B = \{ \langle M \rangle \mid M \text{ halts on at least one input} \}$$
Here, we can choose $M_1$ as
$M_1:$ "On input $x$, if $x = aa$ then reject, else loop forever"
and $M_2$ as
$M_1:$ "On input $x$, reject"
Again we have that $\langle M_1 \rangle \in A$ but $\langle M_2 \rangle \notin A$, while we also have $L(M_1) = L(M_2)$.
A correct application of Rice's theorem to a decision problem about Turing machines must identify a non-trivial class of Turing-recognizable languages that the decision problem corresponds to.
See my note http://people.cs.aau.dk/~hans/ANoteOnRicesTheorem.pdf for more about correct applications of Rice's theorem as well as a discussion of incorrect applications of the theorem.
Context
StackExchange Computer Science Q#65277, answer score: 5
Revisions (0)
No revisions yet.