Rice’s Theorem – Intro to Theoretical Computer Science


Now the proofs for showing undecidability are somewhat easier than showing NP completeness, because basically, what we are doing is the following. We start out with saying that for any computer program, we can decide a certain property and then derive from that but then you could solve the halting problem. And you have seen that this works with a lot of properties. So deciding if the program will stop doesn’t work, deciding if the program is equivalent to another program doesn’t work, deciding if the program even does what it’s supposed to do doesn’t work. Even though you might still feel somewhat cheated by the original halting problem proof, you might be inclined to think that once you accept that then there’s actually not much you can decide about the properties of a program at least in general, and it turns out that that is exactly true. In 1953, Henry Rice after whom Rice’s Theorem is named proofed that basically you cannot use an algorithm to decide anything about the properties of a given program. So we must be a little bit more formal about this property x thing here. And Henry Rice used the notion of a functional property here. Now, what is a functional property? Sounds very complicated. Actually, it’s a very simple definition. Any functional property has these two properties. First, it describes how the output relates to the input. So this is what we mean by behavior and that is important to how they relate to each other not for example how much time we need or something like that. And the second property is that there must be some programs that have this property, and other programs that don’t have this property. So that when you look at all possible computer programs, some of them will have this property others won’t so that it can basically distinguish between the two.

2 Comments

Add a Comment

Your email address will not be published. Required fields are marked *