4 ms·
We're demonstrating that we've solved the problem as stated, not demonstrating that the halting problem can be solved. There is no time frame for how long your
by markessien 18y ago
We're demonstrating that we've solved the problem as stated, not demonstrating that the halting problem can be solved. There is no time frame for how long your test program can run (in the clients wishes), so even if there is an infinite loop in the program fed in - your own test program also waits infinitely. Because your program never stops, and is basically still doing it's job, the client cannot tell you that your solution is wrong. He can only tell you that your solution is wrong if you return a wrong answer, but you never do.
So while the halting problem cannot be solved, the clients requirements can be fulfilled (logically).
- neilc 18y agoThe 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 :-)
- fdb 18y ago"Bureaucrat Conrad, you are technically correct – the best kind of correct."
- lliiffee 18y agoSo your claim is that we can satisfy the requirements thus: (?) while 1, {} Not sure if you meant this, but remember that it is not possible to write a program that always gives the correct answer, just in an unpredictably large amount of time.