Best approach for Undecidability proof

Question

Context:

Hi, my professor sent me this challenge and I got stuck. I thought using Rice's Theorem for this question, since $M$ is non-trivial, but he told me to use a reduction.

Is he right? Should I try to follow his advice or try my own?

Question

Let $M$ be a Turing machine and for every non-trivial property $X$ in a semidecidable language we define the following decision problem:

Is it true that the language $\textrm{ACCEPT}(M) \cup \textrm{REJECT}(M)$ satisfies the property $X$?

Prove that the decision problem is undecidable.

So far:

I was told to build a reduction $r$ using Property Testing for $X$ that for every instance $M$ builds another instance $M'$ that satisfies the following:

$$\text{ACCEPT}(M) \cup \text{REJECT}(M)$$

How should I proceed?

Answer 1

I assume that $\text{ACCEPT}(M)$ denotes the set of strings accepted by Turing machine $M$, and similarly that $\text{REJECT}(M)$ denotes the set of strings rejected by Turing machine $M$. The decision problem must have a parameter and be

Given a Turing machine $\langle M \rangle$, is it true that the language $\textrm{ACCEPT}(M) \cup \textrm{REJECT}(M)$ satisfies the property $X$?

Let us call this new decision problem $\mathcal{N}_X$. Moreover, when we speak of properties, the usual definition is that a property $X$ is a family of semidecidable languages.

Rice's theorem tells us that for any non-trivial property $X$, the decision problem $\mathcal{R}_X$

Given a Turing machine $\langle M \rangle$, is it true that $\textrm{ACCEPT}(M) \in X$?

We can easily reduce $\mathcal{R}_X$ to $\mathcal{N}_X$ by the following reduction:

Given an $\mathcal{R}_X$ instance $\langle M \rangle$, build the machine description of a machine $M'$ that behaves as follows:

On input $x$

1. Simulate $M$ with input $x$.
2. If $M$ accepted, then accept.
3. Else loop forever.

Clearly, $\textrm{ACCEPT}(M') = \textrm{ACCEPT}(M)$ and $\textrm{REJECT}(M') = \emptyset$ and therefore $\textrm{ACCEPT}(M') \cup \textrm{REJECT}(M') = \textrm{ACCEPT}(M)$.