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

53 Views Asked by At

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

1

There are 1 best solutions below

5
On BEST ANSWER

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.