What is the problem with stopping?

Question

Whenever people ask about the stop problem, as it relates to programming, people answer "If you just add one loop, you have a stop program and therefore you cannot automate the task"

Has the meaning. If your program has an infinite loop, then when your program is running, you cannot find out if the program continues to crunch input, or if it is simply cyclically infinite.

But some of them seem counterintuitive. What should I do if I write a stop problem solver using the source code as the source code. rascher@localhost$ ./haltingSolver source.c

If my code (source.c) looks like this:

 for (;;) { /* infinite loop */ } 

It seems to be very easy for my program to see this. “Look at the loop and look at the condition. If the condition is based only on literals and variables, then you always know the result of the cycle. If there are variables (for example, while (x <10)), see if these variables ever change. If no, then you always know the result of the cycle. "

Of course, these checks will not be trivial (calculating pointer arithmetic, etc.), but this does not seem impossible. eg:

 int x = 0 while (x < 10) {} 

. along with - although not trivially:

 int x = 0 while (x < 10) { x++; if (x == 10) { x = 0 } } 

What about user input? This is a kicker, that's what makes the program unpredictable.

 int x = 0; while (x < 10) { scanf("%d", &x); /* ignoring infinite scanf loop oddities */ } 

Now my program can say: "If the user enters 10 or more, the program will stop. It will start again on all other inputs."

This means that even with hundreds of inputs, one should be able to list the conditions under which the program will stop. Indeed, when I write a program, I always make sure that someone has the opportunity to stop it! I am not saying that the created list of conditions is trivial to create, but for me this does not seem impossible. You can enter data from the user, use them to calculate index indices, etc. - but this simply adds to the number of conditions guaranteeing the completion of the program, does not make it impossible to list them.

So what is the problem with stopping? What I don’t understand is that we cannot write a problem to detect infinite loops? Or, why are "loops" such often cited examples?

UPDATE

So let me change the question a bit: what is the problem with stopping, how does this relate to computers? And then I will answer some of the comments:

Many said that the program must deal with "any arbitrary input." But computers do not have a single arbitrary input. If I enter only one byte of data, then I have only 2 ^ 8 possible inputs. So, as an example:

 int c = getchar() switch (c) { case 'q': /* quit the program */ } 

Suddenly I just explained all the possibilities. If c has a bit pattern of 0x71, it does one thing. For all other templates, it does something else. Even a program that accepts arbitrary line input is never "arbitrary", since the resources are finite, which means that although the theory of "arbitrary" is applied ... it is not entirely individual with practice.

Another example people refer to:

 while (n != 1) if (n & 1 == 1) n = 3 * n + 1; else n /= 2; 

If n is a 32-bit integer ... then I can visually tell you if this will stop.

I think this edit does not ask anything, but the most convincing example I've seen is this one :

Suppose you have a magic program / method to determine if a program is stopping.

 public bool DeterminesHalt(string filename, string[] args){ //runs whatever program you tell it do, passing any args //returns true if the program halts, false if it doesn't } 

Now let's say that we are writing a small piece of code, for example ...

 public static void Main(string[] args){ string filename = Console.ReadLine(); //read in file to run from user if(DeterminesHalt(filename, args)) for(;;); else return; } 

So, for this example, we can write a program to make the exact opposite of our magic stop method. If we somehow determine that a given program will stop, we simply jump into an endless loop; otherwise, if we determine that the program is in an infinite loop, we end the program.

And again, if you intentionally write a program containing an infinite loop ... "Solving the problem with stopping" is a moot point, right?

Answer 1

EDIT (much later than the original answer): MarkCC Good Math, Bad Math recently wrote an excellent discussion on the problem of stopping with specific examples.

The problem with stopping is basically a formal way of asking if you can tell whether the arbitrary program will eventually end.

In other words, can you write a program called the oracle, HaltingOracle (program, input), which returns true if the program (input) eventually terminates, and which returns false if it is not?

The answer is no, you cannot.

The following questions about whether the input signal to the stop problem are relevant or red herring: Yes, the input is very important. In addition, there seems to be some confusion in what I see that “infinite” is used where “arbitrary” is more correct.

A practical example . Imagine that you are working in a QA position, and you have to write a stop check program (aka oracle), which will confirm that for any arbitrary program written by the development team (D) and any arbitrary input provided by the end user (I), program D will eventually stop when you enter input I.

Cue manager voice: “Ho ho, these stupid users, let's make sure that no matter what type of garbage they collect, our server tasks will never end up in an endless loop. Do so, monkey code!”

That seems like a great idea, right? You do not want your server to freeze, right?

What the problem of stopping tells you is that they are entrusting you with an unsolvable task. Instead, in this particular case, you need to plan tasks that are completed over a threshold time and be prepared to cancel them.

Mark uses code instead of input to illustrate the problem:

 def Deciever(i): oracle = i[0] in = i[1] if oracle(Deceiver, i): while True: continue else: return i 

In my discussion in the comments, I took the path of malicious input manipulation to cause an unsolvable problem. Mark's example is much more elegant, using an oratory to defeat himself:

So, entering Deceiver is actually a list of two elements: the first is the proposed oracle. the second is another entrance. What kind of stop the killer is to ask Oracle: "Do you think I will stop to enter i?". If the oracle says: “Yes, you halt,” then the program goes into an endless loop. If the oracle says, “No, you are not stopping,” then he is stopping. what the oracle says, its wrong.

Speaking in a different way, without cheating, reformatting the inputs, counting / countless infinities, or anything else distraction, Mark wrote a piece of code that can defeat any oracle stop program. You cannot write an oracle that answers the question of whether Deceiver stops.

Original answer:

From the great Wikipedia :

In computability theory, a stop problem is a solution problem, which can be formulated as follows: given the description of the program and the final input, decide whether the program ends running or runs forever, taking into account the input.

Alan Turing proved in 1936 that a common algorithm for solving the problem of stopping the problem for all possible programmatic inputs of a pair cannot exist. We say that the problem with stopping is insoluble Turing machines. Copeland (2004) attributes the actual stop date to the problem with Martin Davis.

One of the critical points is that you do not control either the program or the input. Those are handed to you, and it is up to you to answer the question.

We also note that Turing machines are the basis for efficient computability models. On the other hand, everything you do in modern computer languages ​​can be compared with these archetypal Turing machines. As a result, the problem of stopping is insoluble in any useful modern language.

Answer 2

To solve the stop problem, you need to develop an algorithm that could determine if any arbitrary program will stop for any arbitrary input , and not just the relatively simple cases in your examples.

Answer 3

Here is a simple explanation of the proof that the stop problem is unsolvable.

Suppose you have a program H that calculates whether the program stops. H takes two parameters, the first is the description of the program, P, and the second is the input, I. H returns true if P stops at input I, and false otherwise.

Now write a program, p2, which accepts when it enters a description of another program, p3. p2 calls H (p3, p3), then a loop if H returns true and stops otherwise.

What happens when we run p2 (p2)?

It must loop and stop at the same time, as a result of which the Universe will explode.

Answer 4

It is so beaten to death that in fact there is poetic evidence written in the style of Lewis Carrolloud> Dr. Seuss Jeffrey Pullum (he is Knowledge of the magazine ).

Funny stuff. Here's the taste:

Here's the trick that Eid uses - and it's easy to do.
Ill define a procedure that I will call Q,
that will use Ps predictions of cessation of success
to cause a terrible logical mess.

...

No matter how P can execute, Q will dig it out:
Q uses the output of Ps to make P look stupid.
No matter what P says, he cannot predict Q:
P is right when he is mistaken, and is false when his is true!

Answer 5

There is confirmed OK problem with a stop on Wikipedia.

To accurately illustrate why simply applying some technique to loops is not enough, consider the following program (pseudo-code):

 int main() { //Unbounded length integer Number i = 3; while(true) { //example: GetUniquePositiveDivisiors(6) = [1, 2, 3], ...(5) = 1, ...(10) = 1, 2, 5, etc. Number[] divisiors = GetUniquePositiveDivisiors(i); Number sum = 0; foreach(Number divisor in divisiors) sum += divisor; if(sum == i) break; i+=2; } } 

Can you come up with an approach that will return true if this code stops, and false otherwise?

Think carefully .

If you happen to meet for the Fields medal, imagine the following code for these problems instead.

Answer 6

"If you just added one loop, you have a stop program, and therefore you cannot automate the task."

Sounds like someone who generalizes the application of the stop problem. There are many special cycles that you can stop. There is research that can perform completion checks for wide classes of programs. For example, in Coq you are limited to programs that you can terminate. Microsoft has a Terminator research project that uses various approximations to prove that programs will stop.

But, remember, the problem with stopping is not only examples of toys. None of them solves the common problem with stopping because they do not work for every program.

The problem is that the stopping problem indicates that there are programs that you don’t have a way of knowing if they will end without starting them, which means that you will never be able to decide whether to stop them.

An example of a program that may or may not be stopped (in Haskell):

 collatz 1 = () collatz !n | odd n = collatz (3 * n + 1) | otherwise = collatz (n `div` 2) 

or in something more accessible:

 while (n != 1) if (n & 1 == 1) n = 3 * n + 1; else n /= 2; 

For every integer> = 1, will this program stop? Well, it has worked so far, but there is no theorem that says it will stop for every whole. We have a hypothesis due to Lothar Collatz , which dates from 1937, but it does not contain evidence.

Answer 7

Regarding the sub-item "people respond" If you just add one cycle, you have a stop program, and therefore you cannot automate the task, "I will add this detail:

Posts that say that you cannot algorithmically calculate whether an arbitrary program will be stopped are absolutely true for the Turing machine.

The fact is that not all programs require Turing machines. These are programs that can be calculated using a conceptually “weaker” machine — for example, regular expressions can be fully implemented by a state machine that always stops at the input. Isn't that nice?

I argue that when people say “add one loop,” they try to express the idea that when a program is complex enough, it requires a Turing machine, and thus the problem of stopping (like an idea) is applied.

This may be slightly tangent to the question, but I think that given this detail in the question, it’s worth noting. :)

Answer 8

Turing's good example was self-referential — suppose there is a program that can examine another and determine if it will stop. Submit the ITSELF check-stop program to the stop check program - what should I do?

Answer 9

Here is a program that the problem of stopping can never be solved.

Suppose you have a magic program / method to determine if a program is stopping.

 public bool DeterminesHalt(string filename, string[] args){ //runs whatever program you tell it do, passing any args //returns true if the program halts, false if it doesn't } 

Now let's say that we are writing a small piece of code, for example ...

 public static void Main(string[] args){ string filename = Console.ReadLine(); //read in file to run from user if(DeterminesHalt(filename, args)) for(;;); else return; } 

So, for this example, we can write a program to make the exact opposite of our magic stop method. If we somehow determine that a given program will stop, we simply jump into an endless loop; otherwise, if we determine that the program is in an infinite loop, we end the program.

No matter how many input checks you do, there is no possible solution to determine if any program is written or not.

Answer 10

Many interesting concrete examples / analogues. If you want to read deeper in the background, there is a good book on Turing's original paper, Annotated Turing, Charles Petzold.

There is a really neat essay in a related, side-shaped, vein, on the Internet, Who can name a larger number? which clicks on Turing machines and Ackerman functions.

Answer 11

There are already many good answers, but I have not seen anyone pay attention to the fact that in some sort of random mix of theory and practicality, the problem of stopping is really solvable.

So, first of all, the problem with stopping is basically writing a program that accepts any arbitrary second program and determines whether the secondary program will stop at random input. So you say: “Yes, this program will stop at this input” or “No, it will not.” And in fact, this is unsolvable in the general case (other people seem to have already proved this) on a Turing machine. The real problem is that you can find out if something stops running it (just wait until it stops), but you can't really find out if something stops running it (you just keep waiting always).

This is a problem on a Turing machine, which by definition has an infinite amount of memory and, therefore, infinitely many states. However, our computers have a limited amount of memory. There are so many bits on a computer. Therefore, if you can somehow track all of the previous states (bit configurations) that you saw during program startup, you can ensure that your control panel never enters an endless loop. If the secondary program eventually stops, you say: "Yes, this program will stop at this input." If you see the same bit configuration twice before it stops, you know "No, it won't." It probably does not have much technical significance, but it’s good to know that many times the “difficult” problems that we face are more difficult in theory than in practice.

Answer 12

This is a variant of the problem of stopping the dog , with the exception of programs instead of dogs and stopping instead of barking.

Answer 13

You have indicated some simple cases.

Now think about all the other cases.

There are an infinite number of possible scenes, you will need to list them.

Unless, of course, you can generalize it.

This is where the stopping problem arises. How did you generalize it?

Answer 14

: http://en.wikipedia.org/wiki/Halting_problem , http://en.wikipedia.org/wiki/Halting_problem#Sketch_of_proof , , .

Answer 15

Collatz ?

Answer 16

,

4.6

5. , , x .

 while x != 1 do if even(x) x = x/2 else x = 3*x +1 

Answer 17

, , , .

.

Answer 18

, , : - - ,

. , . , , , , :

BBC h2g2

, , rentacoder.com. ATuring, .:)

Answer 19

, , , , .

Answer 20

One more example. , .

 f(n) is odd - f(n+1) = 3*f(n)+1 f(n) is even - f(n+1) = f(n)/2 

, 1, 4,2,1,4,2,1,4,2,1... . , , - , 1.

, . , , / , . , , , , .

Answer 21

; , ( , , , , ).

, , , , , . , 70 , , - , , , .