3 ms·
I think Rice's theorem is a big hammer here: it's equivalent to the halting problem because one can just test extensional equality of given M: simulate M;
by JadeNB 7y ago
I think Rice's theorem is a big hammer here: it's equivalent to the halting problem because one can just test extensional equality of
given M: simulate M; return 1
and
given M: return 1
Or is it even true of extensional equality for _total_ functions?
- jerf 7y ago"I think Rice's theorem is a big hammer here" It is certainly a big hammer, but as theoretical computer science tools go, it is pleasingly easy to use. Unfortunately it is pleasingly easy to use in much the same way high explosives are pleasingly easy to blow yourself up with, as it annihilates so many things that we'd rather like to keep. But, still... easy to use.