That's a beautiful lightning rod for finding the people you would never hire for a real project :)
Solve the halting problem, $300-$1000
71–80 of 86 posts
Re: Solve the halting problem, $300-$1000
#72I love those kinds of sites. A month ago I Googled my site name and found someone asking for a clone of my site (which is pretty complex and involve clustering and automated categorization - http://esciencenews.com ) for 250-750$. I laughed a lot, then I cried a little inside at how much people value software and IT skillset in general.
Re: Solve the halting problem, $300-$1000
#73",[.]" 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 " S…
What you are missing is: 1) Analyzing a function's behavior sometimes (frequently) takes as long as running the function itself, 2) some functions can run forever, and 3) sometimes we can't tell the functions that run forever from those that run a very long time.
Example: Write a simple function F to generate prime numbers. (Search the internet for examples if you've never tried it. It can be done in a few lines with two loops.) Your prime-number-generating function F will never halt, because it will never run out of integers to check -- i.e. because there are infinite integers to be tested for being prime. So the halting problem is solvable for F, it is known that F will never halt.
Now slightly modify function F to notice whenever it has generated two primes in a row that are only two away from each other, such as 11 and 13. Increment a counter C whenever these Twin Primes are detected. This is as simple as storing the previous prime P1, subtracting it from the newly-generated prime P2, and seeing if P2-P1 is equal to 2. Finally, make one last tiny change to your function: accept a parameter X, and halt when the counter C becomes greater than X. At this point the function F is probably less than ten lines long and not very complicated at all. I get to pick X for you. Can you write an analyzer function A to decide if function F(X) halts or not?
The answer is: No, you can't. To write function A you would have to prove or disprove the Twin Prime Conjecture, which mathematicians have been trying to do and failing at for centuries.
http://en.wikipedia.org/wiki/Twin_prime_conjecture
Lets imagine that the Twin Prime Conjecture is wrong and there are a finite number of Twin Primes, N. We've been searching for N for so long that I'm confident than N is very, very large, whatever it is. Meaning I can pick an X that is less than N, but still so large that function F(X) will take longer than our lifetime to generate that many Twin Primes and halt. Alternately, lets imagine that the Twin Prime Conjecture is correct and there are infinitely many Twin Primes. Again, I can pick an X so large that it will take longer than our lifetime for F(X) to halt. Either way, we would both be dead before knowing the results of the test, and maybe the test will never complete, who can say?
Worse, any analyzer function A you could write would have to know N to decide if F(X) will halt or not. But N is not known and has not yet been discovered after hundreds of years of trying. So function A would either have to disprove the Twin Primes Conjecture (unlikely with anything less than artificial intelligence) or it would have to calculate C by generating all the primes that F(X) would generate, meaning that A is equivalent to F, meaning that A is no faster than F.
Therefore, neither you nor any currently-conceivable function A can decide if function F(X) will halt or if F(X) will continue searching forever. That's the halting problem and it's unsolvable for this F(X).
Re: Solve the halting problem, $300-$1000
#74Earlier quoted context omitted.
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…
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.
Re: Solve the halting problem, $300-$1000
#75Earlier quoted context omitted.
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.
Then you're prejudiced against me.
Re: Solve the halting problem, $300-$1000
#76Re: Solve the halting problem, $300-$1000
#77Re: Solve the halting problem, $300-$1000
#78Earlier quoted context omitted.
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 inpu…
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…
"Bureaucrat Conrad, you are technically correct – the best kind of correct."
Re: Solve the halting problem, $300-$1000
#79I think that the biggest boon to the users of GetACoder is the fact that this clearly demonstrates who the idiots on the site are.
I mean, take the first bid, the "kagtech" group/person. Not only are they obviously bidding automagically, but obviously doing so quite successfully enough to pay for a premium account.
There's nothing wrong with outsourcing to India in my opinion, but outsourcing to Idiotistan is worthy of a punishment that can only be delivered by an Idiotistan "coder."