Talk:Rice's theorem

This  level-5 vital article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Mathematics Low‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles Low This article has been rated as Low-priority on the project's priority scale.

(cur) (last) . . 21:59 8 Jun 2003 . . Rzach (The comments didn't make sense and the claims made (eg that it is decidable if an algorithm halts after 3 billion steps) were false)

Isn't it decidable if an algorithm halts after 3 billion steps? Can't you test it by running it for 3 billion steps? كسيپ Cyp 22:05 8 Jun 2003 (UTC)

It's decidable if the algorithm runs in less than 3 bn steps on a given input, but not if it runs in less than 3bn steps on all inputs. Rice's Thm is about properties of partial functions not about algorithms, and even less about algorithms and inputs. But I do see the problem with the statement of the theorem now: it's trivial propoerties of partial functions not of algorithms that are at issue Rzach 22:25 8 Jun 2003 (UTC)

If the set of possible inputs at each step is finite (and it is... you often input one bit at a time, i.e. two possibilities), then whether or not a program always halt after at most 3 billion steps is perfectly decidable from a computability point of view. Just run all 3 billion steps on all possible input strings (they are in finite number).

Of course, it's impossible in practice, but that's another problem. See model checking. David.Monniaux 16:48, 18 Nov 2004 (UTC)

A recent addition to the page says:

Another way of stating this problem that is more useful in computability theory is this: if there exists a Turing machine that has a certain property, and a Turing machine which does not have it, then the problem of taking a Turing machine and deciding whether it has that property is undecidable.

As stated, this is false. Consider the property of having exactly 17 states. Clearly Turing machines exist which do and which do not possess this property, and the property is obviously decidable. This is why Rice's theorem is usually stated about the partial functions that the machines compute, or about the languages that they accept: it is only nontrivial behaviors that are undecidable.

I am about to remove this paragraph from the article until such time as the author chooses to repair it. -- Dominus 13:50, 24 Sep 2004 (UTC)

I'm sorry, I forgot the important condition the property be a property of the language recognized, rather than the machine (that is, any two machines recognizing the same language agree on the property.) Thanks for catching this. I wasn't watching this page, so that's why my response was unsuitably delayed. Derrick Coetzee 05:09, 31 Oct 2004 (UTC)

The page says:

The algorithm is simple: we construct a new program t which (1) temporarily ignores its input while it tries to execute program a on input i, and then, if that halts, (2) returns the square of its input. Clearly, t is a function for computing squares if and only if step (1) halts.

This is true for the squaring program, but say we were trying to decide if a given function never halts. Then, although t does compute the function if step (1) halts in this case, it still computes the function even if a doesn't!

I've been pondering how to fix it, but I'm not sure what way is best. One way is to separately prove it in the case where the function that never halts has the property, using the fact that we have a function available that doesn't have the property. I'm going to proceed with this approach. Derrick Coetzee 06:37, 31 Oct 2004 (UTC)

Deciding whether "a given function never halts" is the same as deciding the halting problem, which is known to be undecidable, and thus does not constitute a hole in the proof. Even if it did, your addition seems to be original research and would require citation. -- Ben-Arba 05:56, 7 September 2007 (UTC)[reply]

I found this part confusing! Isn't the proof based on reducing any non-trivial property to "trying to decide if a given function never halts"... Are there any examples of properties that have this problem, but are not already assumed to be undecidable? —Preceding unsigned comment added by 217.159.166.81 (talk • contribs)

from which matematicians?

More significantly, isn't the Rice-Myhill-Shapiro theorem a different theorem, which states properties of computably enumerable functions, and hence provides a simple method to prove functions are not computably enumerable? I think the reference to the R-M-S theorem should be omitted or completely rewritten.

I did Google search for "rice-myhill-shapiro"; several of the top (non-Wikipedia) hits make clear that someone thinks that Rice's theorem is known by this name:

• Notes from U Mass professor Arnold ROsenberg "The Rice-Myhill-Shapiro Theorem (One can say virtually nothing about the dynamic behavior of a program based only on its description..."
• NIST technical calendar "according to the Rice-Myhill-Shapiro Theorem, all non-trivial properties of functions are undecidable."

But someone should probably come up with a reference that is known to predate Wikipedia. -- Dominus 13:27, 18 November 2006 (UTC)[reply]

The article states:

For example, asking whether a machine runs for more than 100 steps on some input, whether it has more than 5 states, or whether it ever moves its tape head to the left are all nontrivial but decidable properties.

However, the third example (whether the head ever moves to the left) is undecidable. If it were decidable, the halting problem would also be decidable. You can construct a Turing machine that emulates the behaviour of another machine exactly except that it only ever moves the head to the left of the initial starting square if the other machine halts. Then being able to decide if this machine ever moves to the left means you can decide if the emulated machine ever halts.

I don't think your analysis is correct. The question isn't whether a Turing machine moves its head to the left of the initial square---which I agree is undecidable---but whether it moves its head to the left at all. Your proposed machine T that moves to the left of the initial square only of some other machine S halts can be constructed, but it can't be constructed in such a way that that left move is the only one it ever executes. -- Dominus 13:40, 13 June 2006 (UTC)[reply]

To see why, let M be a TM that simulates an arbitrary TM N by first reading the description of N and its input onto a work tape of M. Obviously this copying can be done moving the input tape head only to the right. If N halts, then M moves its input tape head once to the left and halts. Then this reduces the halting problem for N to the problem of asking whether M ever moves its input tape head to the left; i.e., this is undecidable. I have removed this claim from the main text. Perhaps you meant something like the question of whether any of the tape heads ever moves left, or whether the tape head on a one-tape TM ever moves left, which I believe are decidable. If this is what you meant and want to re-add it, I suggest stating precisely what you mean and adding justification for it. Pexatus 15:10, 26 October 2006 (UTC)[reply]

Neither this article, nor the article computable function adequately define the notion of what a "properpty of a computable function" is. In the informal discssion, this is somwhat vague, and a concrete example or two would help. (funny that counter-examples, of things that are not properites, are given). Next, in the formal definition section, it is implied that a "property of a computable function" is isomorphic to a "subset of all computable functions" -- but without a formal definition of a "property of a computable function", this is not quite clear. linas 00:06, 27 July 2006 (UTC)[reply]

Shouldn't this say, more accurately:

The set ..., with the Cantor pairing function, is not recursive. In other words there exists no total computable function to decide if any pair of Gödel numbers reference the same computable function.

(This set may not be recursively enumerable, but you can't conclude that from Rice's Theorem.)

The statement "It is important to note that Rice's theorem does not say anything about properties of machines, only of functions and languages." is literally wrong and I'm about to change it.

As an example that it is wrong, conside the following statement about Turing machines: "No Turing machine can decide the general problem of whether another Turing machine will print the number '42' as its result." This is both a true statement about machines and a consequence of Rice's Theorem. Rice's Theorem in fact has lots of useful things to say about machines and programs, albeit indirectly.

The sentence as it stands uses a common standard rhetorical device, and in another context something like "I'm not talking about George, I'm talking about his cat." would not have to be restated as "I speak only of George insofar as he stands in his relationship of owner to his cat." But in this context I think the sentence demands to be interpreted literally not rhetorically. And its literal interpretation is wrong.

--Jeffreykegler (talk) 14:37, 14 May 2008 (UTC)[reply]

The following sentence from the lede makes no sense:

"...there exists at least one algorithm for which it is undecidable whether the algorithm computes a partial function with this property."

For any particular algorithm, either it does or does not compute a partial function with the desired property, and thus either the constant 0 function, or the constant 1 function, correctly decides the question for that particular algorithm.

More generally, saying that a decision problem is undecidable means that there is no function that, whenever given any possible instance of the problem, correctly makes the decision. But each particular instance either does or does not have the desired property. So it doesn't make sense to say that a particular instance is not decidable, it only makes sense to say that the problem as a whole is not decidable. This is because decidability is explicitly about the existence of a procedure to test an arbitrary instance for the desired property. — Carl (CBM · talk) 03:13, 27 October 2008 (UTC)[reply]

"The constant 0 function" is another, different algorithm. Algorithm here is equivalent to partial function, and the properties spoken of are properties of partial functions. Example properties (where input and output are treated as integers): "Does it ever return the number 42 for any input?" "Does a even input ever produce an odd output?"

For the constant 0 function, the answer to the both questions is "no". For the constant 1 function, the answer to the first question is no, and the answer to the second question is "yes" because the constant 1 function, with 2 as its input, has 1 as its result.

Now consider the partial function, UTM, which emulates a universal Turing machine, where the input is its program. It is a particular partial function and can be implemented as a particular algorithm. Consider properties of the form "Does the input x produce any output?" (Since we're dealing with partial functions, that's a live question.) This of course, is the Halting Problem, which is undecidable. There is no procedure to test the particular algorithm (partial function) UTM for arbitrary instances of that very important property.

The reason the excluded middle does not apply here, is that we're talking about decidability, not truth. Yes, every UTM either eventually halts or it doesn't. But that fact does not help us decide which of the two is the case.

--Jeffreykegler (talk) 05:37, 27 October 2008 (UTC)[reply]

You're not seeing what I'm saying. Suppose that you give me a fixed algorithm x, and for concreteness say we're worried whether x halts. Excluded middle says either x halts or x does not halt. Thus either the constant 0 function gives the correct answer to "Does x halt?" or the constant 1 function gives the correct answer to that question. Even if we don't know which of the two is correct, the existence of at least one correct answer means that the question "Does the specific algorithm x halt" is decidable. This is true for any particular algorithm x. What is also true is there is no single decision procedure that works correctly for all algorithms x.

So, like I was saying - it doesn't make any sense to talk about a specific instance of a decision problem being decidable. It only makes sense to say that the entire decision problem is decidable, or the entire decision problem is undecidable.

Yet another way of seeing what I'm saying is to look at the definition of "noncomputable set" that underlies the definition of "undecidable problem". A set X is noncomputable if for each algorithm e there is at least one number n such that e gives the wrong answer to "Is n in X?". This is not the same as saying "There is some number m such that it is undecidable whether m is in X". For any particular m there will indeed be some algorithm that correctly tells whether m is in X, and so that particular question will be decidable (although for some values of m we may not know which algorithm gives the correct answer). — Carl (CBM · talk) 07:35, 27 October 2008 (UTC)[reply]

Jeff, if I might call you that, I think you're mixing up two senses of the word decidable here. A decision problem is "decidable" if there's an algorithm that solves it — this has nothing to do with whether we know in which way it solves it.

It's easy to get confuse this sense of the word with the quite distinct sense in which, say, the continuum hypothesis is "undecidable in ZFC", meaning that ZFC neither proves it nor refutes it, a fact that has led some (quite unjustifiably IMO, but that's not important right now) to conclude that "we can't know" whether it's true or false. Even if they were right about that, it's still an entirely different sense of the word. --Trovatore (talk) 09:43, 27 October 2008 (UTC)[reply]

The above paragraph "More generally, saying that a decision problem is undecidable means that there is no function that, whenever given any possible instance of the problem, correctly makes the decision. But each particular instance either does or does not have the desired property. So it doesn't make sense to say that a particular instance is not decidable, it only makes sense to say that the problem as a whole is not decidable. This is because decidability is explicitly about the existence of a procedure to test an arbitrary instance for the desired property." is much clearer than the existing introduction in undecidable problem. Perhaps the undecidable article should be improved, based on the above material, and rice's theorem can simply point at it. Derek farn (talk) 10:08, 27 October 2008 (UTC)[reply]

This section is getting long, so I'm creating a new one: "Rice's Game". By the way, have you ever wondered what Wikipedia does about "race conditions" in edits? I just found out. Loser in the race condition has his edits disappear without a trace. But having to retype the whole thing from memory forced me to state things more clearly, I hope.  :-) --Jeffreykegler (talk) 11:08, 27 October 2008 (UTC)[reply]

Ok, I see. You're using the constant functions as decision procedures. But that's specifically excluded by the formulation of Rice's Theorem. Only "non-trivial" properties are subject to Rice's Theorem. "Trivial" in the Rice's context means always true or always false -- in other words, having as their correct decision procedure a constant function.

Perhaps the theorem is more clearly stated as a Game. In Rice's Game, Abelard is required to come up with a property of partial functions (his choice) and a decision procedure. Abelard's decision procedure must accept an algorithm from his adversary, Eloise, as input. Abelard's decision procedure must return 0 or 1, according to whether Eloise's algorithm computes a partial function with Abelard's choice of property. The rules forbid Abelard to submit a constant function as his decision procedure.

Eloise wins if she can produce a specific example of an algorithm, for which Abelard's decision procedure gives a wrong answer. If Eloise fails to do this, Abelard wins.

In Rice's game, Eloise always has a win. She can take Abelard's decision procedure and diagonalize it. (I can give details of how she does it, but the proofs in the article already do this.)

Yes, if Abelard were allowed his choice of property and either constant function 0 or constant function 1 as his decision procedure, Abelard could always win. But Abelard is specifically forbidden to do that.

The current article states: "for any non-trivial property of partial functions, there exists at least one algorithm for which it is undecidable whether the algorithm computes a partial function with this property". I believe that's correct and that the two proofs in the article show that. Eloise always has a win.

-Jeffreykegler (talk) 11:17, 27 October 2008 (UTC

Changing to a game based description is a good idea. I completely understand Rice's theorem. My concern is with the literal wording of the sentence in the lede. The formal statement saying that Eloise has a guaranteed win is: "for any decision procedure that Abelard produces, Elosie can find some algorithm that causes it to give the incorrect answer." In particular, Abelard plays first and Eloise plays second.

The article incorrectly claims that Eloise can produce a single algorithm that will always let her win no matter what procedure Abelard comes up with. In other words, it claims that Eloise can win when playing first. Clearly, if Eloise plays first, then Abelard has the possibility of making Eloise lose, if he happens to guess the correct constant function as a decision procedure. Thus Eloise cannot guarantee a win if she is forced to play first.

But the article currently says: "for any non-trivial property of partial functions, there exists at least one algorithm for which it is undecidable whether the algorithm computes a partial function with this property." In other words, it says there is a single algorithm that Eloise can always play to win. It should say "for any non-trivial property of partial functions, there is no decision procedure that correctly tells whether arbitrary programs compute a function with that property." In other words, the sentence needs to actually mention Abelard's move, and make sure it is put in the correct order in the game. — Carl (CBM · talk) 13:09, 27 October 2008 (UTC)[reply]

Ok. We're completely in agreement on what Rice's Theorem says. Yes, if the lede says that Eloise plays first, then Eloise loses and the lede is wrong.

I am open to new language which is clearer than the current language. The language of your change was not clear to me, and in my reading the current language is clear and correct. I see now that the placement of "for which it is undecidable" in the current language can suggest alternative and incorrect readings.

How about the following: "for every non-trivial property of partial functions, there is no procedure that can, in general, decide correctly whether an algorithm computes a function with that property." ("In general" splits the verb from its modal, which might bug some prescriptivist grammarians, but I hope nobody cares what they think. It's the clearest placement for it.)

Even better might be less stuffy language. Something like "Take any non-trivial property of partial functions. Is there a decision procedure that, for any algorithm whatsoever, can tell us correctly whether that algorithm computes a partial function which has that property? Rice's Theorem says that the answer is no. No procedure correctly decides the property for all algorithms."

--Jeffreykegler (talk) 18:28, 27 October 2008 (UTC)[reply]

I like the phrase "any algorithm whatsoever", it removes the various possible interpretations of "in general". Otherwise either form is ok with me (although the second is probably too personalized). Derek farn (talk) 18:38, 27 October 2008 (UTC)[reply]

Re Jeff, the text I had put in the article before was "for any non-trivial property of partial functions, there is no effective method to decide whether a given algorithm computes a partial function with that property." You suggest "for every non-trivial property of partial functions, there is no procedure that can, in general, decide correctly whether an algorithm computes a function with that property." Either is fine with me. Re Derek: adding an extra word like "whatsoever" or "arbitrary" in front of "algorithm" is also fine with me. — Carl (CBM · talk) 19:17, 27 October 2008 (UTC)[reply]

How about this? "... for any non-trivial property of partial functions, there is no general and effective method to decide whether an algorithm computes a partial function with that property. Here, a property of partial functions is called trivial if it holds for all partial computable functions or for none. An effective decision method is called general if it decides correctly for every algorithm."

I used CBM's change as the template, adding the adjective "general" to describe the method. I define "general" afterwards, in another sentence. I put the definition of "general" after that for "trivial", because otherwise the "Here" starting the sentence defining trivial becomes awkward. That "here" is important because it indicates that the sense in which the word "trivial" is used in defining Rice's theorem is specific to Rice's theorem.

--Jeffreykegler (talk) 20:40, 27 October 2008 (UTC)[reply]

OK, that sounds good. I copied that to the article. The first sentence seemed too long so I moved the bibliographic info to a later sentence. Also, I noticed the Rice-Shapiro theorem article claimed Stewart Shapiro instead of Norman Shapiro. Stewart was not born until 1951, and Rogers (1967) references "N. Shapiro", at which time Stewart would have been 16 years old... — Carl (CBM · talk) 21:05, 27 October 2008 (UTC)[reply]

Would the following proof also work?

Let ${\displaystyle \phi \colon \mathbb {N} \to \mathbf {P} ^{(1)}}$ be a Gödel numbering of the (partial) computable functions.

Suppose that ${\displaystyle F}$ is a set of (partial) computable functions such that ${\displaystyle \emptyset \neq F\neq \mathbf {P} ^{(1)}}$. Then there exist ${\displaystyle g\in F}$ and ${\displaystyle g'\notin F}$. Suppose that there is a computable function ${\displaystyle f}$ that decides ${\displaystyle F}$; then there is a number ${\displaystyle n}$ such that ${\displaystyle \phi _{n}(x)}$ computes ${\displaystyle f(n)}$ and returns ${\displaystyle g'(x)}$ if the result is "yes," ${\displaystyle g(x)}$ otherwise. But then, ${\displaystyle \phi _{n}\in F\iff \phi _{n}\notin F}$; contradiction.

The halting problem can then be seen as a special instance of Rice's theorem?

Thanks, Benja (talk) 00:39, 5 January 2009 (UTC)[reply]

Quite elegant. And (while I'm not a professional) on first reading it looks right to me.

One thing. It might help if you add, after the proof as an explication, what exactly happens when ${\displaystyle \phi _{n}(x)}$ is called for various x. Rice's Theorem is of wide interest. A professional won't need to be hit over the head on how the diagonalization works, a reader for whom this is not their daily meat and drink could use a little extra help. --Jeffreykegler (talk) 01:35, 5 January 2009 (UTC)[reply]

Right. That makes it more complicated, the halting problem is probably more widely known... What we would need, it seems to me, is the corollary to Kleene's recursion theorem. Suppose that ${\displaystyle F}$ is decidable; then, there exists a function ${\displaystyle Q(x,y)}$ that returns ${\displaystyle g'(y)}$ if ${\displaystyle \phi _{x}\in F}$, ${\displaystyle g(y)}$ otherwise. By the corollary, there is an index ${\displaystyle e}$ such that ${\displaystyle \phi _{e}(y)}$ returns ${\displaystyle Q(e,y)}$. But then, if ${\displaystyle \phi _{e}\in F}$, then ${\displaystyle \phi _{e}}$ is the same function as ${\displaystyle g'}$, and therefore ${\displaystyle \phi _{e}\notin F}$; and if ${\displaystyle \phi _{e}\notin F}$, then ${\displaystyle \phi _{e}}$ is ${\displaystyle g}$, and therefore ${\displaystyle \phi _{e}\in F}$. In both cases, we have a contradiction. -- Maybe it would be a good idea to add it as an alternative proof, leaving the one from the halting problem in place. I'm not sure. Benja (talk) 05:38, 5 January 2009 (UTC)[reply]

Also: I think more explanation of that notation which isn't defined in readily accessible places within Wikipedia may be in order. We'd want the proof to be accessible to, at the very least, someone who studied Theory of Computation in school, but is rusty. In particular, that ${\displaystyle \mathbf {P} ^{(1)}}$ is the set of partial functions of degree 1 might not be immediately clear to someone, and I don't know how you'd look that up quickly. Wikipedia-internal links can be used for the commoner terms like "Gödel numbering" and "partial function".

I know what I'm complaining about was also in the previous version, but while you're fixing things. :-) --Jeffreykegler (talk) 02:11, 5 January 2009 (UTC)[reply]

I removed the following:

On the other hand, the statement that "No modern general-purpose computer can solve the general problem of determining whether or not a program is virus free" is a consequence of Rice's Theorem because, while a statement about computers, it can be reduced to a statement about languages.

(Unfortunately, outside formal computer science, this consequence has been misunderstood as implying that no algorithm can reject all virus-containing programs: This property is vacuously true of an algorithm that rejects all programs, and is known^{[citation needed]} to be true of algorithms that, for all computations of practical interest, will accept some programs that perform that computation.)

It lacked verification, but more importantly, Rice's theorem is not applicable to the question as stated.

A program for a pure Turing machine cannot be a virus, because all it does is take data as input and give data as output. It can only act as a virus if you then execute (some part of) its output. In other words, the concept of a virus is not applicable to a pure computation model such as a Turing machine model; it only makes sense in an interactive computation model that includes I/O [for example, reading and writing to a filesystem that is accessible to other programs].

Of course, Rice's Theorem applies to any pure computation done by some subprogram. This means, for instance, that if a program is running in an environment where whether it acts as a virus (for any definition of what a virus is) depends in some nontrivial way on its behaviour, then a checker working on its code cannot in general decide whether or not it will have that behaviour. Perhaps that is what the statement intended to say.

OTOH, that's a rather vacuous application of Rice's theorem that doesn't really shed any light on anything. In particular, it doesn't shed any light on the possibility of solving the problem of viruses in practice. To do that, you need to run programs in an environment where the program doesn't have the authority to do any harm. That can be enforced without having to decide any nontrivial properties of its computational behaviour. --David-Sarah Hopwood ⚥ (talk) 05:17, 18 December 2010 (UTC)[reply]

Where did j in formal proof and the picture next to it came from? Pitel (talk) 09:58, 29 January 2012 (UTC)[reply]

It is the input to algorithm T in the proof. This algorithm is generated dynamically by H during its execution. — Carl (CBM · talk) 12:51, 29 January 2012 (UTC)[reply]

I don't see how committing array bounds errors is a semantical property. While I don't know how to define such errors for a Turing machine, informally, it seems to me like for every program with an implementation that doesn't violate array bounds, there is always another implementation of the same program that does: Violate one in the beginning, then execute the original implementation. Of course, this assumes that the execution continues after a violation — but if it doesn't, the example is just a horribly misleading word game and restatement of the halting problem itself, rather than a noteworthy application of Rice's theorem. 109.44.0.4 (talk) 18:24, 14 October 2017 (UTC)[reply]

> It implies that it is impossible, for example, to implement a tool that checks whether a given program is correct, or even executes without error

This is wrong isn't it? It implies that it's impossible to make such a tool that can determine whether *any* program is correct, but there are plenty of tools that can determine that *some* programs are correct.

Perhaps "a given program" should be changed to "any program". 94.174.71.191 (talk) 09:59, 17 November 2024 (UTC)[reply]