Hacker News Reader

Comment by markessien | Hacker News Reader

Unfortunately, the person who put up the project did not specify that the solution has to complete within a timespan. So given a piece of code, a proposed solution could just try all possible values, trying to discover if it will halt. This may take very long.

If the project client complains, he will need to prove that your solution is wrong, and he cannot prove that if he does not give your solution enough time to try all possible combinations.

View on HN

Assuming Alan is using a Turing-complete language, how exactly do you propose to "just try all possible values"? Given an infinite loop, what values are you trying?

And it's a freshman problem to prove that the halting problem is undecidable. (It's also in about a million CS and math textbooks.)

You could always just say "To demonstrate that your program works, show the output of it running on itself, given this input..."

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).

"Bureaucrat Conrad, you are technically correct – the best kind of correct."

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.

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?

>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 :-)

Suppose 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.

No, 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.

So 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.

http://en.wikipedia.org/wiki/Termination_analysis

imo they really should stop teaching the halting problem to freshmen. At least not without some practical results accompanying the theory.

That's not all, he has not mentioned what language the programs will be in.

Reply on news.ycombinator.com