Skip to main content
Computer Science

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

3
  • $\begingroup$ I can't get this answer.. (Sorry if I'm asking the same, but would be good to clarify this point). It says you can modify those programs by changing their syntax to get an extensional equivalent, but how to check those are extensional equivalent in the first place? You cannot use a program to compare if those programs functions in general have both that property, so when you say "modify it" I think it's possible because are simple examples, (would you add "modify it carefully"? or use a "good IDE for it"?..) I think once is modified you can't check in general so, perhaps Rice holds. $\endgroup$ Commented Jun 16, 2014 at 18:22
  • 2
    $\begingroup$ In general you check that two particular programs are extensionally equal by proving that this is the case. Do you object to the fact that $n + m = m + n$ for all integers, even though a computer cannot "check" this equality for all values? Hopefully not. There is a difference between writing a program that computes a boolean value, and proving that a certain statement has a certain truth value. There are things we can prove but cannnot compute (such as the fact that two particular programs are extensionally equal, or that addition is commutative). $\endgroup$ Commented Jun 17, 2014 at 7:48
  • 1
    $\begingroup$ Also, you are commiting a weird leap of reasoning in your reasoning: since extensional equality is not decidable, Rice's theorem might be false. How so? And just because extensional equality is undecidable, that does not mean there aren't any instances of it which we can decide. The ones I mentioned -- we can decide those. $\endgroup$ Commented Jun 17, 2014 at 7:50