1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What are $f_m$ and $f_M$? (I assume one of them is a typo, but what does the other one mean?) $\endgroup$ – David Richerby Jan 25 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 Jan 25 at 17:01
0
$\begingroup$

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.

$\endgroup$

Your Answer

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

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