HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is the Rice Theorem applicable for these problems?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thethesefortheoremapplicableproblemsrice

Problem

I have 1 problem :-->

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.

Context

StackExchange Computer Science Q#65277, answer score: 5

Revisions (0)

No revisions yet.