0
$\begingroup$

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

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .