Talk:Rice's theorem

From Wikipedia, the free encyclopedia

(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)

Contents

[edit] Computability theory formulation

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)

[edit] Error in informal proof

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)

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)

[edit] The Rice-Myhill-Shapiro theorem

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:
But someone should probably come up with a reference that is known to predate Wikipedia. -- Dominus 13:27, 18 November 2006 (UTC)

[edit] Undecidable Problems

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)
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)

[edit] property of a computable function

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)

[edit] Wording of example

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.)

[edit] Rice's Theorem's Relevance to Machines and Programs

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)