Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Solve the halting problem, $300-$1000

getacoder.com

Post reply on HN
Print view View original

61–70 of 86 posts

Re: Solve the halting problem, $300-$1000

#61

Post by shard »

chollida1 wrote: post #57
shard wrote: post #44

Earlier quoted context omitted.

If I ran into a black guy on the street and he mugged me then I'm sure going to remember it. In fact if the topic comes up I'll probably tell people "Don't run into black guys, they'll mug you".

If you actually say "Don't run into this particular black guy, because he mugged me" then your statement is equivalent to mine, and wouldn't be racist, just a statement of fact. :)

Hmm... I think that if you had said "Don't eat at the McDonalds at 451 Lexington Ave, because they make bad hamburgers" then it would be equivalent to "Don't run into this particular black guy, because he mugged me".

>=)

Re: Solve the halting problem, $300-$1000

#62

Post by markessien »

neilc wrote: post #60
markessien wrote: post #54

Earlier quoted context omitted.

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 you…

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?

Re: Solve the halting problem, $300-$1000

#65

Post by neilc »

markessien wrote: post #62
neilc wrote: post #60

Earlier quoted context omitted.

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?

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.

Re: Solve the halting problem, $300-$1000

#66

Post by narag »

markessien wrote: post #62
neilc wrote: post #60

Earlier quoted context omitted.

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

Re: Solve the halting problem, $300-$1000

#67

Post by icky »

vegashacker wrote: post #33

One way to satisfy AlanT's spec is to choose a "non-standard" language to write this this "Bug Finder" for. If the language has the strong normalization property ( http://en.wikipedia.org/wiki/Normalization_property ), then the requested debugger is quite simple: (define (halt? p) #t) (As for error checking, assuming this means, say, type errors, I think if you choose a language like the typed lambda calculus that's…

If you look at "sleep"'s response:

Dear Sir, You have found the right person to do the job. I am a representative of a company that has recently completed a large enterprise commercial project related to the development of a HaltLib.NET library that is meant specifically to solve the problem of interest to you, and I am ready to share my experiences and code. Note that our library works for a wide variety of programming languages, including, but not limited to, HTML, XML, PNG, CSV, SQL, BNF, Regular Expressions and even "Field=Value" .property file formats. I guarantee you maximally efficient and clean code on this project.

You'll note that he doesn't list any Turing-complete languages. (The implementation will almost certainly look like yours). :P

Re: Solve the halting problem, $300-$1000

#68

Post by Allocator2008 »

",[.]"

That is a BrainF*k program. It reads a char (","), then if value is greater than 0 (i.e. not null since ANSI 0 is 48, so more precisely, if the input is not null, rather than greater than 0), then in that case it enters the square brackets. It outputs the entered char ("."). It does not decrement the value in that cell ("-"), it does not add to it ("+"), it does not move the pointer to another cell (">" or "Seems to me, go thru a program source code, and look at all loops and see if the pointer controlling the loops ever decrements the cell it is pointing to. If it does, program terminates. If it doesn't program does not terminate. If cell pointer is at overflows its capacity program blows up. There. I just solved the requirements of the "get a coder" posting. That will be 300 euros please (because the dollar sucks). :-)

More seriously, I think in terms of the requirements, it is not a matter of running f(x). It is a matter of analyzing f(x). Maybe you can't do this for all x, but surely it seems like you can for all f. Meaning, you can't test an infinite number of inputs to a given input program. But you can go thru the source code, like the above example, and determine how it will handle the input x. Feeding x into the f above will give you an infinite loop. You don't know that if all you do is feed x to f. But if you look at f first and you look at x (in this case, to know x is not null), then you can predict f(x) will infinite loop, without ever having to run it.

In other words the requirements are not asking for a debugger. They are asking for an oracle, i.e., an "intelligence" in the program smart enough to look at f, look at x, and figure ok f never stops, f does stop, or f blows up. The oracle won't run f(x). The oracle will merely analyze f(x). And she does this by simply looking for while type loops, and figuring out the affect x will have on the pointers controlling them. Will x cause the cell pointed to by the pointer to get decremented to the point of stopping an infinite loop or not? If so, f(x) halts, if not, it doesn't. Gosh, this doesn't sound so impossible (again, viewing the requirements as really asking for an oracle, not a debugger). Maybe I'm missing something here, and would welcome comments.

Re: Solve the halting problem, $300-$1000

#69

Post by mleonhard »

a-priori wrote: post #34
LogicHoleFlaw wrote: post #32

Earlier quoted context omitted.

My father designs HVAC systems for nuclear missile silos. I was asked him about how the embedded controls software works, and how they handle error conditions. The biggest concern? EMP blasts. The solution? Mechanical failsafes.

This is the solution in other high-reliability systems as well. You develop to as strict standards as are feasible, then provide provisions (e.g. watchdog timers and replication) for when it fails.

And supervisor processes, as in Erlang.

Re: Solve the halting problem, $300-$1000

#70

Post by shard »

cousin_it wrote: post #58
shard wrote: post #44

Earlier quoted context omitted.

If I ran into a black guy on the street and he mugged me then I'm sure going to remember it. In fact if the topic comes up I'll probably tell people "Don't run into black guys, they'll mug you".

What if you got mugged by most black guys you met? Do you think outsourcing to faraway places has a success rate of over 50%? Would you bet money on this? And I'm speaking as someone from a faraway place who once lived off outsourcing. Price competition on your hourly rate sucks, but it was the only realistic way we could make money.

If you got mugged by most black guys you met, I would be questioning how and why you are specifically selecting black muggers to meet.
Post reply on HN