How to prove undecidability other than Rice Theorem?

Question

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.

Answer 1

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.

Answer 2

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.