سؤال

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