Rice Rice Baby

I donโ€™t understand Riceโ€™s Theorem and itโ€™s killing me.

Lord there is indeed some big confusion here. Itโ€™s amazing that people like this can do math that I could never do but canโ€™t understand things that seem fairly simple to me, like Riceโ€™s Theorem.

Riceโ€™s Theorem doesnโ€™t have much to do with the real world as this person is imagining it. Itโ€™s only about how languages and such work in some idealized world. How it does relate to the real world is that itโ€™s all about why there is no general algorithm (decision procedure) that can look at a computer program and for anything non-trivial determine what itโ€™s going to do. To determine that, you have to run the damn program. Thatโ€™s in a nutshell all that Riceโ€™s Theorem means.

Anything that happens in finite time is decidable, by the way. Whether a program halts after 10 steps or 4,000 steps is the same is if you have pizza or a hamburger for lunch tomorrow. This is what I mean by Riceโ€™s Theorem doesnโ€™t have much to do with our reality. You are running the program, so you are โ€œdecidingโ€ all the time!

Where RT relates to the halting problem is that like that problem, it just means that there isnโ€™t any method to evaluate all programs in advance to see if they halt or just run infinitely. Hereโ€™s an infinite loop in Python:

i=0
while i

Nothing about that violates the laws of physics but it'll go till the computer breaks or till the universe ends -- whichever comes first. But (assuming this were actually more complex example), you don't know that until you run the program -- and it halts. Or does not, as is the case with this one.

In the real world of programming, Rice's Theorem actually deals with more complex features, but the above is a good-enough that is not brain-breaking.

Rice's Theorem is often interpreted by people to mean: we can't determine anything about programs. Which is wrong. Run them, and you have determined. QED.