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.

Improve this question
$\endgroup$
2
  • $\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
    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

Reset to default
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.

Improve this answer
$\endgroup$

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.