4 ms·
The job of the program is to return true or false; until it does that, it can't be said to be "basically doing its job" if it never terminates. The client might
by neilc 18y ago
The job of the program is to return true or false; until it does that, it can't be said to be "basically doing its job" if it never terminates. The client might also not be able to tell you that a solution of "while (true) ;" is "wrong" because it never returns the wrong answer, but that isn't a solution either.
- markessien 18y agoOkay, imagine a program that takes 100 years to complete, before returning true. My program has to wait 100 years to return its result, but it will return the result correctly. Now, assuming that my program runs correctly, how can the client prove that my program does not work, and hence deny me the payment?
- neilc 18y agoSuppose the analysis program is given an input that fails to terminate. The client expects your program to indicate this fact after a finite time, but your program will not be able to do so in the general case. In any case, looking at individual test cases is not the point. The client is justified in asking for a proof that your program detects non-termination for all possible input programs in the language. Since no such proof can exist, you don't get paid. The burden of proof is on the person proposing the solution, not the client.
- markessien 18y agoNo, he's asking for a program, not a proof. The point I'm making is that it's possible to fulfill the guys request without solving the halting problem, because you can inteprete his request in ways he did not intend. The request did not include any 'finite time' specification.
- narag 18y ago>Now, assuming that my program runs correctly, how can the client prove that my program does not work, and hence deny me the payment? He can put an offer in GetACoder asking for a program that proves that :-)