Rice’s theorem (a.k.a. computational irreducibility) says that for most algorithms, the only way to figure out what they’ll do with certainty is to run them step-by-step and see.
Rice’s theorem says nothing of the sort. Rice’s theorem says:
For every semantic property P,
For every program Q that purports to check if an arbitrary program has property P,
There exists a program R such that Q(R) is incorrect:
Either P holds of R but Q(R) returns false,
or P does not hold of R but Q(R) returns true
Notice that the tricky program R that’s causing your property-checker Q to fail is under an existential. This isn’t saying anything about most programs, and it isn’t even saying that there’s a subset of programs that are tricky to analyze. It’s saying that after you fix a property P and a property checker Q, there exists a program R that’s tricky for Q.
for most algorithms, the only way to figure out what they’ll do with certainty is to run them step-by-step and see
This is only sort of true? Optimizing compilers rewrite programs into equivalent programs before they’re run, and can be extremely clever about the sorts of rewrites that they do, including reducing away parts of the program without needing to run them first. We tend to think of the compiled output of a program as “the same” program, but that’s only because compilers are reliable at producing equivalent code, not because the equivalence is straightforward.
a.k.a. computational irreducibility
Rice’s theorem is not “also known as” computational irreducibility.
By the way, be wary of claims from Wolfram. He was a serious physicist, but is a bit of an egomaniac these days. He frequently takes credit for others’ ideas (I’ve seen multiple clear examples) and exaggerates the importance of the things he’s done (he’s written more than one obituary for someone famous, where he talks more about his own accomplishments than the deceased’s). I have a copy of A New Kind of Science, and I’m not sure there’s much of value in it. I don’t think this is a hot take.
for most algorithms, the only way to figure out what they’ll do with certainty is to run them step-by-step and see
I think the thing you mean to say is that for most of the sorts of complex algorithms you see in the wild, such as the algorithms run by brains, there’s no magic shortcut to determine the algorithm’s output that avoids having to run any of the algorithm’s steps. I agree!
I was gonna say that you’re nitpicking, but actually, I do want this post to be correct in detail and not just in spirit. So I edited the post. Thanks. :)
Rice’s theorem is not “also known as” computational irreducibility.
OK, I no longer claim that. I still think it might be true, at least based on skimming the wikipedia article, but I’m not confident, so I shouldn’t say it. Maybe you know more than me. Oh well, it doesn’t really matter.
By the way, be wary of claims from Wolfram
Yeah, I think “computational irreducibility” is an intuitive term pointing to something which is true, important, and not-obvious-to-the-general-public. I would consider using that term even if it had been invented by Hitler and then plagiarized by Stalin :-P
Yeah, I think “computational irreducibility” is an intuitive term pointing to something which is true, important, and not-obvious-to-the-general-public. I would consider using that term even if it had been invented by Hitler and then plagiarized by Stalin :-P
Agreed!
OK, I no longer claim that. I still think it might be true
No, Rice’s theorem is really not applicable. I have a PhD in programming languages, and feel confident saying so.
Let’s be specific. Say there’s a mouse named Crumbs (this is a real mouse), and we want to predict whether Crumbs will walk into the humane mouse trap (they did). What does Rice’s theorem say about this?
There are a couple ways we could try to apply it:
We could instantiate the semantic property P with “the program will output the string ‘walks into trap’”. Then Rice’s theorem says that we can’t write a program Q that takes as input a program R and says whether R outputs ‘walks into trap’. For any Q we write, there will exist a program R that defeats it. However, this does not say anything about what the program R looks like! If R is simply print('walks into trap'), then it’s pretty easy to tell! And if R is the Crumbs algorithm running in Crumb’s brain, Rice’s theorem likewise does not claim that we’re unable tell if it outputs ‘walks into trap’. All the theorem says is that there exists a program R that Q fails on. The proof of the theorem is constructive, and does give a specific program as a counter-example, but this program is unlikely to look anything like Crumb’s algorithm. The counter-example program R runs Q on P and then does the opposite of it, while Crumbs does not know what we’ve written for Q and is probably not very good at emulating Python.
We could try to instantiate the counter-example program R with Crumb’s algorithm. But that’s illegal! It’s under an existential, not a forall. We don’t get to pick R, the theorem does.
Actually, even this kind of misses the point. When we’re talking about Crumb’s behavior, we aren’t asking what Crumbs would do in a hypothetical universe in which they lived forever, which is the world that Rice’s theorem is talking about. We mean to ask what Crumbs (and other creatures) will do today (or perhaps this year). And that’s decidable! You can easily write a program Q that takes a program R and checks if R outputs ‘walks into trap’ within the first N steps! Rice’s theorem doesn’t stand in your way even a little bit, if all you care about is behavior after a fixed finite amount of time!
Here’s what Rice’s theorem does say. It says that if you want to know whether an arbitrary critter will walk into a trap after an arbitrarily long time, including long after the heat death of the universe, and you think you have a program that can check that for any creature in finite time, then you’re wrong. But creatures aren’t arbitrary (they don’t look like the very specific, very scattered counterexample programs that are constructed in the proof of Rice’s theorem), and the duration of time we care about is finite.
If you care to have a theorem, you should try looking at Algorithmic Information Theory. It’s able to make statements about “most programs” (or at least “most bitstrings”), in a way that Rice’s theorem cannot. Though I don’t think it’s important you have a theorem for this, and I’m not even sure that there is one.
Oh sorry, when I said “it might be true” just above, I meant specifically: “it might be true that ‘computational irreducibility’ and Rice’s theorem are the same thing”. But after a bit more thought, and finding a link to a clearer statement of what “computational irreducibility” is supposed to mean, I agree with you that they’re pretty different.
Anyway, I have now deleted all mention of Rice’s theorem, and also added a link to this very short proof that computationally-irreducible programs exist at all. Thanks very much :)
Rice’s theorem says nothing of the sort. Rice’s theorem says:
Notice that the tricky program
Rthat’s causing your property-checkerQto fail is under an existential. This isn’t saying anything about most programs, and it isn’t even saying that there’s a subset of programs that are tricky to analyze. It’s saying that after you fix a property P and a property checker Q, there exists a program R that’s tricky for Q.There might be a more relevant theorem from algorithmic information theory, I’m not sure.
Going back to the statement:
This is only sort of true? Optimizing compilers rewrite programs into equivalent programs before they’re run, and can be extremely clever about the sorts of rewrites that they do, including reducing away parts of the program without needing to run them first. We tend to think of the compiled output of a program as “the same” program, but that’s only because compilers are reliable at producing equivalent code, not because the equivalence is straightforward.
Rice’s theorem is not “also known as” computational irreducibility.
By the way, be wary of claims from Wolfram. He was a serious physicist, but is a bit of an egomaniac these days. He frequently takes credit for others’ ideas (I’ve seen multiple clear examples) and exaggerates the importance of the things he’s done (he’s written more than one obituary for someone famous, where he talks more about his own accomplishments than the deceased’s). I have a copy of A New Kind of Science, and I’m not sure there’s much of value in it. I don’t think this is a hot take.
I think the thing you mean to say is that for most of the sorts of complex algorithms you see in the wild, such as the algorithms run by brains, there’s no magic shortcut to determine the algorithm’s output that avoids having to run any of the algorithm’s steps. I agree!
I was gonna say that you’re nitpicking, but actually, I do want this post to be correct in detail and not just in spirit. So I edited the post. Thanks. :)
OK, I no longer claim that. I still think it might be true, at least based on skimming the wikipedia article, but I’m not confident, so I shouldn’t say it. Maybe you know more than me. Oh well, it doesn’t really matter.
Yeah, I think “computational irreducibility” is an intuitive term pointing to something which is true, important, and not-obvious-to-the-general-public. I would consider using that term even if it had been invented by Hitler and then plagiarized by Stalin :-P
Agreed!
No, Rice’s theorem is really not applicable. I have a PhD in programming languages, and feel confident saying so.
Let’s be specific. Say there’s a mouse named Crumbs (this is a real mouse), and we want to predict whether Crumbs will walk into the humane mouse trap (they did). What does Rice’s theorem say about this?
There are a couple ways we could try to apply it:
We could instantiate the semantic property P with “the program will output the string ‘walks into trap’”. Then Rice’s theorem says that we can’t write a program Q that takes as input a program R and says whether R outputs ‘walks into trap’. For any Q we write, there will exist a program R that defeats it. However, this does not say anything about what the program R looks like! If R is simply
print('walks into trap'), then it’s pretty easy to tell! And if R is the Crumbs algorithm running in Crumb’s brain, Rice’s theorem likewise does not claim that we’re unable tell if it outputs ‘walks into trap’. All the theorem says is that there exists a program R that Q fails on. The proof of the theorem is constructive, and does give a specific program as a counter-example, but this program is unlikely to look anything like Crumb’s algorithm. The counter-example program R runs Q on P and then does the opposite of it, while Crumbs does not know what we’ve written for Q and is probably not very good at emulating Python.We could try to instantiate the counter-example program R with Crumb’s algorithm. But that’s illegal! It’s under an existential, not a forall. We don’t get to pick R, the theorem does.
Actually, even this kind of misses the point. When we’re talking about Crumb’s behavior, we aren’t asking what Crumbs would do in a hypothetical universe in which they lived forever, which is the world that Rice’s theorem is talking about. We mean to ask what Crumbs (and other creatures) will do today (or perhaps this year). And that’s decidable! You can easily write a program Q that takes a program R and checks if R outputs ‘walks into trap’ within the first N steps! Rice’s theorem doesn’t stand in your way even a little bit, if all you care about is behavior after a fixed finite amount of time!
Here’s what Rice’s theorem does say. It says that if you want to know whether an arbitrary critter will walk into a trap after an arbitrarily long time, including long after the heat death of the universe, and you think you have a program that can check that for any creature in finite time, then you’re wrong. But creatures aren’t arbitrary (they don’t look like the very specific, very scattered counterexample programs that are constructed in the proof of Rice’s theorem), and the duration of time we care about is finite.
If you care to have a theorem, you should try looking at Algorithmic Information Theory. It’s able to make statements about “most programs” (or at least “most bitstrings”), in a way that Rice’s theorem cannot. Though I don’t think it’s important you have a theorem for this, and I’m not even sure that there is one.
Oh sorry, when I said “it might be true” just above, I meant specifically: “it might be true that ‘computational irreducibility’ and Rice’s theorem are the same thing”. But after a bit more thought, and finding a link to a clearer statement of what “computational irreducibility” is supposed to mean, I agree with you that they’re pretty different.
Anyway, I have now deleted all mention of Rice’s theorem, and also added a link to this very short proof that computationally-irreducible programs exist at all. Thanks very much :)