Is there a general rule that can be used to determine this? E.g:
int i = 10;
while (i > 1 ) {
if (i%2 == 0) i = i/2;
else i = 3*i - 1;
}
views:
216answers:
3
+12
A:
This is the halting problem. There does not exist an algorithm capable of doing what you ask.
In particular, if there was such an algorithm, then the collatz conjecture, related to the function in your question, would be trivial (or at least a lot easier).
aaronasterling
2010-09-26 06:16:27
Why did this get downvoted? Is it because I was a little off hand with my grammar? I do appreciate the move from 4787 to 4785 though. Round numbers are nice.
aaronasterling
2010-09-26 07:13:31
@UncleO. The title of the question is "How do I check if an algorithm terminates?". The first sentence in the question is "Is there a general rule that can be used to determine this?". This is the halting problem. Don't let the presence of _one_ specific example confuse you. Also note, that OP read my answer and then _selected_ it as answering the question.
aaronasterling
2010-09-26 07:23:14
I thought this was a good answer given the question. +1
JoshD
2010-09-26 08:27:05
@AaronMcSmooth : Upvoted your answer, but don't think that getting the 'accepted answer' somehow makes your answers immune to critique. That's wrong on so many levels I don't know where to begin. An accepted answer can still be shitty, incorrect, misleading, etc etc even if it apparently helped person who asked the question.
Mads Elvheim
2010-09-26 08:55:34
+1
A:
You may be referring to the stopping problem. In short, there is no general way to determine if a program will stop. Check out this article.
JoshD
2010-09-26 06:17:00
Why did this get down-voted? Is it because it's similar to Aaron's answer? We put them up within a few seconds of each other! I'd like feedback...
JoshD
2010-09-26 07:16:56
@UncleO: "How do I check if a program terminates? Is there a general rule that can be used to determine this?" I fail to see how the question, with one example, fails to be a question about the Halting Problem.
Vatine
2010-09-26 08:44:19
+1
A:
In general, "no". As everyone else have said, with your specific example, it can be proven not to terminate, as i is only ever smaller if i is even (or if i is non-positive and odd, but given the initial conditions, that will never happen). The smallest positive even number is 2, this will then turn to 1 for the next iteration, where it will then be turned into 2.
Interestingly, you're not checking the Collatz Conjecture, as you are iterating "halve if even, 3*n-1 if odd" and the Collatz Conjecture iterates "halve if even, 3*n+1 if odd". I can't find this sequence discussed with a quick search.
Vatine
2010-09-26 08:51:34