4 ms·
Okay, 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 r
by markessien 18y ago
Okay, 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 :-)