Timeline for Are there proofs of Rice Theorem without using the undecidability of some problem?
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 2, 2020 at 3:12 | comment | added | user21820 | In particular, one proof that I have seen in many places (for example see here) is more complicated than mine, so unfolding it will give a different longer proof. | |
| Feb 2, 2020 at 3:09 | comment | added | user21820 | @Daniel: Well, in the end every proof of Rice's theorem must pass through some kind of diagonalization. If you look at Joel's proof, the 'diagonalization' is right there in the use of the recursion theorem. I posted my version some time afterward, but it too uses 'diagonalization' right in the "$x(x)$" part. The main advantage of my version is that it corresponds directly to an explicit program I can write (in say Javascript) to defeat any claimed decider. I am not too sure what Noah's comment means, because there are many proofs of Rice's theorem that use the halting problem undecidability. | |
| Feb 1, 2020 at 18:55 | comment | added | Daniel | Isn't this what you would get if you "unfold" the reduction to the halt problem? (as suggested by Noah's comment) | |
| Apr 27, 2014 at 13:40 | history | edited | user21820 | CC BY-SA 3.0 |
Changed "partial function" to "program" for consistency
|
| Apr 27, 2014 at 13:06 | review | First posts | |||
| Apr 27, 2014 at 13:07 | |||||
| Apr 27, 2014 at 12:46 | history | answered | user21820 | CC BY-SA 3.0 |