# Can you prove that the difference of these two undecidable sets is un/decidable?

I'm just an amateur programmer so please bear with me

consider the following sets of numbers $$D=\{m|\text{m is a turing machine and does not halt on blank input}\}$$ $$G=\{m|\text{m is a turing machine and does not halt on m}\}$$ $$L=D-G$$

how can I prove that $$L$$ is un/decidable? thanks

Given a TM $$M$$, we can construct a TM M' running the following program:

1. If the current cell is blank, GOTO 1
2. Simulate M

We find that $$M' \in D \setminus G$$ iff $$M \notin G$$. Thus, if $$D \setminus G$$ were decidable, so would be $$G$$. But $$G$$ is a standard variant of the Halting problem, and so we already know that $$G$$ is undecidable.

• you mean there is a function $f$ such that $G(M)=L(f(M))$ ? Jan 13, 2023 at 11:26
• @raoof It's not mapping $G$ into $L$, but the complement of $G$.
– Arno
Jan 13, 2023 at 11:28
• like $G(M)=1-L(f(M))$ ? but is $f$ computable? Jan 13, 2023 at 11:29
• @raoof Sure, the construction is in the answer.
– Arno
Jan 13, 2023 at 11:44
• how do you prove that $L$ is/not recursively enumerable? Jan 13, 2023 at 12:17