Solve the halting problem, $300-$1000
getacoder.com
getacoder.com
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.
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..."
So while the halting problem cannot be solved, the clients requirements can be fulfilled (logically).
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.
The request did not include any 'finite time' specification.
He can put an offer in GetACoder asking for a program that proves that :-)
while 1, {}
imo they really should stop teaching the halting problem to freshmen. At least not without some practical results accompanying the theory.
My new mantra is "Don't outsource anything the neighbors' 10 year old couldn't complete properly."
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.
I don't think simple CSS bugs are beyond the skills of even the below-average Indian outsourcing shop (though I'm sure some of them fail even on that level, and depending on how finicky you are about your CSS, maybe no one can do it but yourself).
However, in my experience, the more complicated the task, the less likely it will be to get done via a simple outsourcing contract. A huge consulting company can successfully outsource very complex things, because they can invest in ensuring they hire quality resources.
Someone who has personal contacts with people whom he knows are competent can also do it, because they already know where to find the quality.
For the rest of us, though, there is a sea of bad options (the kind that often charge a few dollars an hour) and a few islets of quality. It's very hard to figure out which ones are the good ones, and these islets get smaller the more your task is complicated. Past a certain level of complexity (e.g. "put together a synchronous framework for a tool like Etherpad") you might as well not bother, your chances of hitting land are so low.
This is not specific to India or Pakistan, it applies to China just as much. Eastern Europe is less of a problem for me because there are fewer communication barriers. My point, clarified, is then: Outsourcing complex tasks to a remote location with which there are communication difficulties is unlikely to work.
Some people, based on past experience, expect to be offended and see malice in words where there is none. Sometimes we make connections between others' statement based on our own beliefs. I guess it's just human nature. It's probably easier to ask for some clarification.
Some people, based on past experience, are unaware that their words may carry unintended malice or hurtfulness (see Rosie O'Donnell's 'Ching Chong' comments) or may harbor subconscious prejudices (see Project Implicit, https://implicit.harvard.edu/implicit/). It's better for all of us that these are pointed out rather than ignored.
If I go to McDonalds and have a bad burger then I'm sure going to remember it. In fact if the topic comes up I'll probably tell people "Don't eat at McDonalds, they make bad burgers".
How is stating ones past experience in any way racist?
I don't think it's unfair to make characterisations based on geographic location. People are not equal, and some nations are definitely "worse" than others in some respect.
Remember that I'm not saying that an Indian in London, for example, would be likely to be more difficult to work with. I know several Indian people in London, and some of them are better coders than me. I'm talking about Indian outsourcing businesses in India, and making an aggregate judgement of what it's like to work with them (not about whether they'll mug you). I think that's fair.
For instance, "Be careful about going on holiday in Somalia" is an equally generalising statement - not all Somali's are pirates or warlords - but it's a fair statement because if you're gonna set foot there, there's a reasonable chance you might meet one of them, so you should be forewarned.
:)
>=)
I'm Eastern European. The logical place to extend that list of countries outside of South Asia would actually happen to be in Eastern Europe. While it would bother me a bit (even though it would be overall more politically correct), it would fall far short of offending me.
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.
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.
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.
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.
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".
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.
Just fabulous.
(Though I bet it was done solely as a joke. Good one, too.)
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."
(define (halt? p) #t)
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
"BTW.. I think it is incredibly ignorant to post such a question with the purpose of mocking those who are not informed on Turing."
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.
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).
I sill can't believe what happened to one of the most influential CS people of all times :-(