14 ms·
Solve the halting problem, $300-$1000
- dhoe 18y agoAn 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.
- henryw 18y agoi 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 18y agoThis response must be from a HN user -- i guess the response is actually a pun. :)
- lani 18y agothe bid one before this guy is from Kurt Godel Himself !!
- swombat 18y agoThis 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 18y agoOne 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."
- swombat 18y agoThat'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.
- alecco 18y agoOutsourcing to a far away place to a random contractor is looking for trouble. But your generalization is offensive.
- jm4 18y agoWhat is offensive about that post? Maybe I'm missing something or others are reading too much into it. He says he would not recommend outsourcing to India, Pakistan, etc., but would consider outsourcing to a qualified firm closer to home. This doesn't necessarily imply that he thinks developers in India and Pakistan are a bunch of dopes. In fact, it doesn't imply anything at all except that he prefers not to outsource overseas. We can really only speculate since he doesn't provide any reasons for his opinion, but maybe we should give him a little more credit here before we jump to conclusions and call the post offensive. His opinions could be explained with a variety of reasons like time difference, difficulty in communicating (either long distance phone calls or having to do everything over email) or even possible language barriers. Sometimes when you need a very specific result you need to be careful how you explain this to someone whose native language is different from your own. Even common figures of speech can be taken literally and result in confusion over what is expected. All of these possible hurdles can be alleviated by working with a group closer to home.
- edu 18y agoProject Creator: Alan T. And the reply by K. Gödel. Made my day.
- amix 18y agoThe 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 18y agohttp://research.microsoft.com/Terminator/ 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.
- deleted 18y ago[deleted]
- cabalamat 18y ago(Said in an Austrian accent:) They'll be back.
- marvin 18y agoThis 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 18y agoMy 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.
- 18y ago
- markessien 18y agoUnfortunately, 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 18y agoThat's not all, he has not mentioned what language the programs will be in.
- ken 18y agoAssuming 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..."
- markessien 18y agoWe'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.
- bcater 18y agoIt 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 http://research.microsoft.com/Terminator/default.htm
- sdfx 18y agolove 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."
- gaius 18y agoI think ernie is ignorant of the meaning of the word ignorant!
- anewaccountname 18y agoIf 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 18y agoFunny, after reading jeff atwood's article on codinghorror (http://www.codinghorror.com/blog/archives/001190.html 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".
- jgrahamc 18y agoI 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 18y agoWell Cantor's diagonalization doesn't have anything to do with it either.
- jgrahamc 18y agoI disagree. In Turing's paper "On computable numbers, with an application to the Entscheidungsproblem" he makes direct reference to diagonalization arguments (section 8 "Application of the diagonal process") alluding to the proof that the real numbers are not enumerable. His proof then relies on a diagonal argument.
- Zaak 18y ago"Despite the fact that I died in 1918 you may find the following advice important." Just fabulous.
- gjm11 18y agoNeat 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.)
- frisco 18y agoThe response by KGodel was classic.
- vegashacker 18y agoOne 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 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 18y agoIf 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 18y agoDude, "sleep" knows PNG! That's the man for the job.
- lisp_hacker 18y agoThe gur "AlanT" is obviously nuts. The halting problem is one that can never be solved.
- frisco 18y agoAlanT is most definitely not nuts.
- sciolizer 18y agoJust gay. :)
- dgordon 18y agoSo, by the standards of his time, nuts.
- ivanstojic 18y agoAn apple a day keeps the gay-healers away. I sill can't believe what happened to one of the most influential CS people of all times :-(
- parenthesis 18y agoWell, I believe the authorities were more concerned about the perceived security risk. Male homosexuality was not decriminalised in England and Wales until 1967 (and not until 1980 in Scotland and 1982 in Northern Ireland). Before that there was the concern that someone like Turing could be blackmailed for state secrets (he played a key role in the wartime code-breaking effort).
- Allocator2008 18y 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 18y agoWhat 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 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 18y agoThat's a beautiful lightning rod for finding the people you would never hire for a real project :)
- FiReaNG3L 18y agoI 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 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 18y agoAnother one: http://www.getacoder.com/projects/programming_c_87390.html http://www.getacoder.com/projects/programming_c_87390.html
- ivanstojic 18y agoI 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 18y agoeasy money, here i come!
- blasdel 18y agoThe replies were all removed, I've mirrored the page pre-moderation: http://www.wabdo.com/fred/bugfinder.html http://www.wabdo.com/fred/bugfinder.html
- frisco 18y agothanks! i was worried that it was lost for a second.