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

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)

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)

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?

The Rice-Myhill-Shapiro theorem

from which matematicians?