Let $L= \{\langle M \rangle \mid M \text{ halts on } \langle M \rangle \} $ be a language where $\langle M \rangle$ is the Code of the TM $M$. $L$ is undecidable.

I've heard that I can't use Rice's theorem to proof its undecidability.

But why? I can construct a set $S = \{f_M \mid f_M(\langle M \rangle)\in \{0,1\}\}$.

It's clear that $S$ is not empty and $S$ contains not every TM.

  • $\begingroup$ What are $f_m$ and $f_M$? (I assume one of them is a typo, but what does the other one mean?) $\endgroup$ Commented Jan 25, 2019 at 16:53
  • $\begingroup$ both should be f_M. It describes the function of the Turing Machine M. 1 and 0 stands for accept or reject. For example the TM M' that accepts everything has the function f_M'(x) = 1 $\endgroup$
    – Marc
    Commented Jan 25, 2019 at 17:01

1 Answer 1


Because there may be multiple $M$'s corresponding to the same $f_M$. That is to say, you cannot deduce $\langle M\rangle$ from $f_M$, so you cannot describe $S$ in this way.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.