Solve the halting problem, $300-$1000(getacoder.com)
getacoder.com
Solve the halting problem, $300-$1000
http://www.getacoder.com/projects/bug_finder_92913.html
22 comments
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..."
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..."
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).
So while the halting problem cannot be solved, the clients requirements can be fulfilled (logically).
"Bureaucrat Conrad, you are technically correct – the best kind of correct."
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 :-)
He can put an offer in GetACoder asking for a program that proves that :-)
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.
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.
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.
The request did not include any 'finite time' specification.
So your claim is that we can satisfy the requirements thus: (?)
while 1, {}
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.
imo they really should stop teaching the halting problem to freshmen. At least not without some practical results accompanying the theory.
That's not all, he has not mentioned what language the programs will be in.
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.
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).
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."
My new mantra is "Don't outsource anything the neighbors' 10 year old couldn't complete properly."
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.
True, but I don't believe this has anything to do with the company being from any particular region. There are very competent development shops in India and very poor ones as well.
Outsourcing to a far away place to a random contractor is looking for trouble. But your generalization is offensive.
What 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.
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.
Maybe I'm reading too much into it, or maybe you missed this point: In response to a post that talked about an outsourced team that didn't even have the technical expertise to handle simple CSS bugs, he said he wouldn't consider outsourcing to India and Pakistan, which implies that those places have the characteristics of not having the technical expertise to handle simple bugs.
Ok, I guess as the original poster of this incendiary comment (?) I can chip in about what I actually meant.
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.
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.
I don't think it's even possible to miss the point I was trying to make more than you already have. I was cautioning against making assumptions about a person who has stated a vague opinion without the reasons for having that opinion. And just like the person I was responding to, you have done exactly that.
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, 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.
What's wonderful about our world is that there are a myriad of ways that people can perceive a situation, which allows all sorts of different viewpoints to emerge. I interpreted the situation differently from you based on my experience of conversation flow, and there's no need for me to agree to your point even though I understood it the first time.
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.
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.
[deleted]
I understand your point, but overuse of the word "offensive" offends me.
There was absolutely no need to name those countries. As somebody said before, the funny thing about racial privilege is how hard it is to see when one is the beneficiary of it.
Perhaps he's had a bad experience with outsourcing to these countries.
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?
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?
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".
I actually wrote India, Pakistan, China, South East Asia... and then replaced it with /etc.
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 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.
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 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".
>=)
>=)
I'm not sure he was doing anything other than giving an eg for the top offshoring locations that popped into his head, in the same way people refer to "Kleenex" when discussing tissues. I see the emphasis is placed on complicated which the italics certainly support. As you also stated, sending complicated projects to people far away is a challenge regardless of the particular country involved. Please stop looking for excuses to be offended.
In the original article most of the bids are from firms located in India.
Like I said, I understand your point, I was making another point about the use of the word "offensive".
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.
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.
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.
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.
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.
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.
This response must be from a HN user -- i guess the response is actually a pun. :)
the bid one before this guy is from Kurt Godel Himself !!
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.
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.
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.
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.
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 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.
(Said in an Austrian accent:) They'll be back.
[deleted]
The 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
thanks! i was worried that it was lost for a second.
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".
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".
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.
"Despite the fact that I died in 1918 you may find the following advice important."
Just fabulous.
Just fabulous.
Well Cantor's diagonalization doesn't have anything to do with it either.
I 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.
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.
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.)
(Though I bet it was done solely as a joke. Good one, too.)
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.
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."
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."
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.
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)
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
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
That's a beautiful lightning rod for finding the people you would never hire for a real project :)
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
The response by KGodel was classic.
Dude, "sleep" knows PNG! That's the man for the job.
easy money, here i come!
",[.]"
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.
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.
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).
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).
The gur "AlanT" is obviously nuts. The halting problem is one that can never be solved.
AlanT is most definitely not nuts.
Just gay. :)
So, by the standards of his time, nuts.
Well, 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).
An 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 :-(
I sill can't believe what happened to one of the most influential CS people of all times :-(
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.