質問

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.

正しい解決策はありません

ライセンス: CC-BY-SA帰属
所属していません cs.stackexchange
scroll top