Solve the halting problem, $300-$1000

http://www.getacoder.com/projects/bug_finder_92913.html

by jcapote • 18 years ago

166 83 18 years ago

dhoe• 18 years ago

An expert team of 70 Webdesigners can get this done in no time. Edit: this is actually an interesting demonstration of what happens if the sales people are disconnected from engineering. I've yet to see a big company that doesn't do the equivalent of this. Slightly more professional, but still the same thing.

Darmani• 18 years ago

I feel that most of these responses were made by bots.

alecco3• 18 years ago

I'm not sure, the amounts vary. The top one at least looks like someone incompetent just guessed a number.

henryw• 18 years ago

i like the last post response:

As the superior German programmer I am I've already solved the problem in my head as per your specification. I'm able to deliver a solution in source code in any language that can print a line of text. If necessary, I can also provide flowcharts and a solution on solid German-made paper.

paraschopra• 18 years ago

This response must be from a HN user -- i guess the response is actually a pun. :)

lani• 18 years ago

the bid one before this guy is from Kurt Godel Himself !!

swombat5• 18 years ago

This is a good demonstration of why you should only outsource things that you could do yourself but don't have the time to do. Never outsource something you don't know how to do (at least not if it's a core competitive requirement).

tdavis• 18 years ago

One time I outsourced the creation of a simple Wordpress template which I didn't have time to do. I paid $300. Despite being given a pre-cut Photoshop file, the people could not figure out simple CSS bugs or even create the CSS necessary for the tabs. I spent more time managing them (aka teaching) than it would have taken me to do it, in the end I had to do half of it anyway and this entire sick ordeal took nearly two weeks.

My new mantra is "Don't outsource anything the neighbors' 10 year old couldn't complete properly."

swombat5• 18 years ago

That's a good point... I wouldn't consider it wise to try and outsource any complicated technology development to India/Pakistan/etc. However, I would consider doing so to an onshore firm that demonstrates to me that they have a clue. For instance, I know plenty of people who take on consulting work and could deal with your CSS without any problems. Depending on how much work was involved, they might even have been able to do it within $300.

kirse• 18 years ago

I wholeheartedly agree. After getting several shoddy outsourced projects I've come to adopt the mantra that "if you want something done right, you've got to do it yourself".

The individual who created a template for me did a decent job on design, but the CSS was absolutely pitiful and full of many unnecessary and confusing layers...

I think this is why large corporations that have detailed processes involving requirements definition etc. do a far better job with getting what they want from outsourced work (as compared to startups). With a 1-2 person company, most of us don't have the time or money to throw together a 50-page whitepaper detailing exactly what is needed.

danw• 18 years ago

There are some fiendishly good psd to html companies out there that produce good css very quickly. I think psd2html is the one I've used reliably in the past.

edu• 18 years ago

Project Creator: Alan T. And the reply by K. Gödel. Made my day.

bdfh42• 18 years ago

Mine too. Geek humour at its best

cperciva• 18 years ago

GeorgesCantor and BusyBeaver also replied.

amix• 18 years ago

The thing to note about the halting problem is that it's impossible to create a general solution that works for all the input programs. That said, one could create an approximative solution and even solve the halting problem for non-turning complete languages.

A lot of the time when we actually solve "hard" problems, we only find approximative solutions (this is for example true when doing static code analysis). Asking does program X have any non-trivial property G is impossible to do in the general case, so we find an approximative solution that can answer this in most of the cases.

Freaky• 18 years ago

http://research.microsoft.com/Terminator/

The ultimate goal of the TERMINATOR project is develop automatic techniques (and tools that implement them) that will allow us to prove that industrial software components cannot hang.

cabalamat• 18 years ago

(Said in an Austrian accent:) They'll be back.

marvin• 18 years ago

This is actually pretty interesting. They aren't claiming that they are trying to make a general solution, just one that works in most cases. It might even be possible, AFAIK there hasn't been very much research in this area.

LogicHoleFlaw• 18 years ago

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.

markessien4• 18 years ago

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.

arjungmenon• 18 years ago

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

ken• 18 years ago

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

markessien4• 18 years 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).

Herring• 18 years ago

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.

bcater• 18 years ago

It has already been linked here, but I think it's worth noting that Cathedral-soft is working on it: http://research.microsoft.com/Terminator/default.htm

sdfx• 18 years ago

love the comment on their discussion board:

"BTW.. I think it is incredibly ignorant to post such a question with the purpose of mocking those who are not informed on Turing."

gaius2• 18 years ago

I think ernie is ignorant of the meaning of the word ignorant!

anewaccountname• 18 years ago

If it is running on a 32 bit machine, and can't make IO calls, you can just enumerate every possible memory/register state and see if the resulting fsa has any loops for the given input range of the function.

Dilpil• 18 years ago

Funny, after reading jeff atwood's article on codinghorror (http://www.codinghorror.com/blog/archives/001190.html), I left a comment suggesting someone do this. I see someone took me up on the offer.

PS, mega points to whoever claimed to know BNF, and also to whoever made the George Cantor post. Also mega points to the creator for using the handle "AlanT".

jgrahamc2• 18 years ago

I am 'GeorgCantor'... I couldn't resist because Gödel's reply seemed lame. He just assumed the undecidability and used it to bang on about his own ideas.

queensnake• 18 years ago

Well Cantor's diagonalization doesn't have anything to do with it either.

Zaak• 18 years ago

"Despite the fact that I died in 1918 you may find the following advice important."

Just fabulous.

gjm11• 18 years ago

Neat way of getting a list of outfits to avoid when you have a real software development task that you want to outsource...

(Though I bet it was done solely as a joke. Good one, too.)

frisco3• 18 years ago

The response by KGodel was classic.

vegashacker• 18 years ago

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

icky• 18 years ago

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

thomasmallen• 18 years ago

Dude, "sleep" knows PNG! That's the man for the job.

lisp_hacker• 18 years ago

The gur "AlanT" is obviously nuts. The halting problem is one that can never be solved.

frisco3• 18 years ago

AlanT is most definitely not nuts.

sciolizer• 18 years ago

Just gay. :)

Allocator2008• 18 years ago

",[.]"

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 "<"). It just sits there and outputs, forever (".") since so long as the value in that cell is not null it will not get out of the square brackets (the "while" loop) and since it never decrements the values ("-") it will always be not null. This is the same as saying "while(true) putchar(c)". This program will not terminate.

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.

shawnyar217• 18 years ago

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

gills• 18 years ago

That's a beautiful lightning rod for finding the people you would never hire for a real project :)

FiReaNG3L• 18 years ago

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

kailashbadu• 18 years ago

Another one: http://www.getacoder.com/projects/programming_c_87390.html

ivanstojic2• 18 years ago

I 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."

annoyed• 18 years ago

easy money, here i come!

blasdel• 18 years ago

The replies were all removed, I've mirrored the page pre-moderation:

http://www.wabdo.com/fred/bugfinder.html

frisco3• 18 years ago

thanks! i was worried that it was lost for a second.

Solve the halting problem, $300-$1000

Related Stories