Is the language $\{ \langle M\rangle | f(\langle M\rangle)=\epsilon\}$ decidable? $f()$ means, that the turing machine returns $\epsilon$ on its own encoding and $\langle M\rangle$ stands for the encoding (a "string-version" of the TM).

I have no idea how I should start. How can I decide, if I use a reduction, a sub program technique or the diagonalizability? I would really appreciate if you could help me, thanks! :)

  • 1
    $\begingroup$ Hint: Given a Turing Machine $M$ you can always define a turning Machine $M'$ that ignores its input, simulates $M$ on the empty input, and when $M$ halts (possibly never), returns $\epsilon$. $\endgroup$ – Steven Nov 13 '19 at 23:21
  • $\begingroup$ "$f()$ means, that the turing machine..." What Turing machine? Do you mean $M(\langle M\rangle)$? $\endgroup$ – xskxzr Nov 14 '19 at 8:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.