# How to prove undecidability other than Rice Theorem?

Im studying Rice Theorem and I would like to verify its consistency. If I am able to prove de undecidability in other ways, the Rice Theorem would prove to be useful after all.

Im trying to find out two different ways to prove that the following Decision problem is undecidable:

Is it true that the Turing Machine $$M$$ accepts exactly a finite and odd number of words?

So far:

One way is using the Rice Theorem. Let $$X$$ be the property of being finite and have an odd number of words. Rice Theorem tells us that for every property of semi-decidable languages, the Test of Property is undecidable only if $$X$$ is non trivial. Now I need to verify if $$X$$ is non-trivial correct? I got stuck on that part.

Talking about other way to prove, I was thinking about Reductio ad absurdum. I have an idea but I don't know how to build this reduction.

If I have an entry $$(M,w)$$ of HALTING that produces $$r(M,w) = M'$$ of ODD.

If $$(M,w)$$ is an affirmative instance of HALTING then $$M'$$ accepts only one word and nothing more. If $$(M,w)$$ is an negative instance of HALTING then $$M'$$ accepts no words at all.

Is that clear? Sorry, english is not my mother language, so translating the way we refer to problems and theorems can be tricky.

Thanks for everything.

• "I would like to verify [Rice's theorem's] consistency. If I am able to prove the undecidability in other ways, then Rice's Theorem would prove to be useful after all." I don't understand this. First of all, what do you mean by "verify its consistency" - do you doubt the validity of the proof? If so, what step(s) seem worrying? Second, a theorem is more useful, not less, if it is indispensable. Commented Nov 20, 2020 at 17:45
• But how to prove a theorem is a theorem? Commented Nov 20, 2020 at 17:47
• I'm not sure what you mean. Have you seen the proof of Rice's theorem? That's how you prove a theorem is a theorem: you prove it. Commented Nov 20, 2020 at 17:48
• I just learned about it and I got interested. I always proved stuff using reduction, so I wanna see if it works better for me keeping this way or using Rice theorem. Commented Nov 20, 2020 at 17:51
• Keep in mind that Rice's theorem itself is proved via a reduction. Basically, what Rice's theorem does is save you from having to write down essentially the same reduction over and over again; it's not a way to avoid reductions, it's a way to avoid redundant effort. Commented Nov 20, 2020 at 17:55

It doesn't really make sense to ask if you can avoid using Rice's theorem by writing down a reduction. This is because Rice's theorem is proved by writing down a reduction - or rather, a general recipe for constructing a reduction - already. Basically, what Rice's theorem does is save you the effort of defining essentially the same reduction over and over again. It's not avoiding reductions, but avoiding redundant effort.

For completeness, let's recall Rice's theorem and its proof. Rather than work with $$HALT$$, I'll work with the many-one-equivalent set of indices of machines which halt on input $$0$$ specifically, and I'll write "$$M_e$$" for the machine with index $$e$$.

Rice's theorem: Suppose $$\mathcal{P}$$ is any nontrivial property of c.e. languages. Then there is a many-one reduction of the halting problem to the set of indices of machines with property $$\mathcal{P}$$.

Proof: Suppose $$\mathcal{P}$$ is a nontrivial property of Turing machines. Let $$M$$ be some Turing machine which never halts on any input. Suppose WLOG that $$M$$ has property $$\mathcal{P}$$ (otherwise work with the complement of $$\mathcal{P}$$ instead). By nontriviality, fix some $$N$$ which does have property $$\mathcal{P}$$. We get a reduction of $$HALT$$ to the index set corresponding to $$\mathcal{P}$$ by - given a number $$e$$ - constructing a machine $$A$$ which behaves as follows:

On input $$x$$, $$A$$ first runs $$M_e$$ on input $$e$$; if it halts, $$A$$ then runs $$N$$ on input $$x$$ and does whatever $$N$$ does.

This $$A$$ behaves identically to $$N$$ if $$e\in HALT$$, and never halts on any input (= behaves identically to $$M$$) otherwise. That is, $$A$$ has property $$\mathcal{P}$$ iff $$e\in HALT$$. So we get a reduction of $$HALT$$ to our index set as desired. $$\quad\Box$$

The key point is that Rice's theorem applies to every nontrivial property of c.e. languages, so there's really no nuance in applying it. This is what makes it useful: when showing that an index set is undecidable, we don't have to think through the details of constructing a specific reduction.

• So what I need to do is to prove that the property X of M is non-trivial, right? How do I do that? Commented Nov 20, 2020 at 18:10
• @Kodora Well, there are two things you need to check. First, you need to prove that $X$ is in fact a property - that is, that two machines which accept the same language either both have property $X$ or both don't have property $X$. Since $X$ is defined directly in terms of the language the machine accepts, this is basically trivial. (It might help demystify things to consider an example of something that isn't a property - say, "halts on input $0$ in at most $5$ steps.") Nontriviality meanwhile just means that some machines have the property and others don't, you just need to find examples. Commented Nov 20, 2020 at 18:14
• Can I apply a Property testing? Commented Nov 20, 2020 at 18:20
• @Kodora I don't know what a "Property testing" is. I think you might want to ask your teacher for some clarification. Commented Nov 20, 2020 at 18:57

There are indeed other ways to prove that the problem is undecidable. However, the technique can be used to prove the more generous Rice's theorem as well.

That is, by virtue of recursion theorem. It allows for a computable process to self-replicate for any Turing machines, which makes the diagonalization technique ready to use under many circumstances.