In particular, it is shown that the Hilbertian Entscheidungsproblem can have no solution.
November 26, 2008 12:09 AM Subscribe
One time I had someone ask why dead code removal couldn't be automated. The answer is that determining whether a given piece of code will ever be executed it's isomorphic to the stopping problem.
Proof: insert a halt in the middle of that piece of code. Will the program execute the halt?
posted by Class Goat at 12:27 AM on November 26, 2008
Proof: insert a halt in the middle of that piece of code. Will the program execute the halt?
posted by Class Goat at 12:27 AM on November 26, 2008
Heh. That was worth a laugh. The specific wording makes me suspect that it might have been posted as a joke, but it could just be delicious irony.
Why didn't he just ask for a program that will take as input a coding problem such as this one, and output the code that solves it? Then he would never have to pay for coding again! Problem solved.
posted by Salvor Hardin at 12:31 AM on November 26, 2008
Why didn't he just ask for a program that will take as input a coding problem such as this one, and output the code that solves it? Then he would never have to pay for coding again! Problem solved.
posted by Salvor Hardin at 12:31 AM on November 26, 2008
The vast majority of the bids are $300. This is the most puzzling part.
posted by maxwelton at 12:39 AM on November 26, 2008
posted by maxwelton at 12:39 AM on November 26, 2008
It's a request for a bug-finding program. Is it worth to be placed on the front page?
posted by susanharper at 12:40 AM on November 26, 2008 [1 favorite]
posted by susanharper at 12:40 AM on November 26, 2008 [1 favorite]
susanharper: It's a joke, really, but one that only programmers will get, most likely. What the job listing is asking for has been proven impossible, as shown by the subsequent links. The humor derives at least in part from the many enthusiastic responses from "top-notch programmer teams" and so on.
posted by Joakim Ziegler at 12:46 AM on November 26, 2008
posted by Joakim Ziegler at 12:46 AM on November 26, 2008
susanharper writes "It's a request for a bug-finding program. Is it worth to be placed on the front page?"
Was that wrong? Should I not have done that? I tell you, I gotta plead ignorance on this thing, because if anyone had said anything to me at all when I first started here that that sort of thing is frowned upon...
Should I have posted this to Jobs?
posted by orthogonality at 1:03 AM on November 26, 2008 [4 favorites]
Was that wrong? Should I not have done that? I tell you, I gotta plead ignorance on this thing, because if anyone had said anything to me at all when I first started here that that sort of thing is frowned upon...
Should I have posted this to Jobs?
posted by orthogonality at 1:03 AM on November 26, 2008 [4 favorites]
Also note that the 'project creator' is given as AlanT.
posted by misteraitch at 1:03 AM on November 26, 2008 [6 favorites]
posted by misteraitch at 1:03 AM on November 26, 2008 [6 favorites]
“Knock, knock.”
“Who’s there?”
very long pause….
“Java.”
posted by netbros at 1:06 AM on November 26, 2008 [39 favorites]
“Who’s there?”
very long pause….
“Java.”
posted by netbros at 1:06 AM on November 26, 2008 [39 favorites]
Project Creator: AlanT
It's the subtle details that make this so marvelous.
posted by nzero at 1:14 AM on November 26, 2008 [2 favorites]
It's the subtle details that make this so marvelous.
posted by nzero at 1:14 AM on November 26, 2008 [2 favorites]
While the earnest and unaware bids have to be the best, I loved this one:
posted by grouse at 2:09 AM on November 26, 2008
BusyBeaver, Lodz, GB, US$1,729 bid amountAlso bids from KurtG, GeorgeCantor, and many, many more.
I will solve your problem in the most productive manner possible.
Bid Time: 11-25-2008 08:28
posted by grouse at 2:09 AM on November 26, 2008
Even better is the first clueful response from KurtG, and then once it was linked to elsewhere; the snark from GeorgeCantor and Busy Beaver.
posted by blasdelf at 2:09 AM on November 26, 2008
posted by blasdelf at 2:09 AM on November 26, 2008
Next up on the MetaFilter Programming Tutorial: race conditions and how to avoid them.
posted by grouse at 2:12 AM on November 26, 2008 [3 favorites]
posted by grouse at 2:12 AM on November 26, 2008 [3 favorites]
It's a request for a bug-finding program. Is it worth to be placed on the front page?It's like posting a request for a perpetual motion machine at an engineer job site, with hordes of Product Managers and Administrators clamoring for the job, waiting with polished buttons and boots to start cracking.
The definition of the problem is something you learn in computer science. Posting this request, put that certain way, surgically splits the population into educated and uneducated. With a neat cracking sound. It is beautiful.
This is an anglerfish with a softly glowing stack of $300 on its nose. Nom nom nom.
posted by krilli at 2:14 AM on November 26, 2008 [12 favorites]
Is this something I'd need a neck-beard to understand?
posted by bardic at 2:22 AM on November 26, 2008 [4 favorites]
posted by bardic at 2:22 AM on November 26, 2008 [4 favorites]
There are only 10 kinds of people in the world. Those that get this joke and those that don't.
This is why there are no Computer Science comedians. Even with thorough documentation and code commenting it takes too long to explain the jokes.
posted by loquacious at 2:28 AM on November 26, 2008 [1 favorite]
This is why there are no Computer Science comedians. Even with thorough documentation and code commenting it takes too long to explain the jokes.
posted by loquacious at 2:28 AM on November 26, 2008 [1 favorite]
As a programmer of the lowest order, not a computer scientist, I have some questions.
This page, linked to in the post, list three programs. One loops a set number of times, one loops a number of times depending on the input, and the last loops forever.
As a human, I can look at these programs an immediately determine which program will do what. I seem to recall that people who are into the theoretical side of this stuff classify problems into those a computer can solve easily but human brains can't (crazy big arithmetic), and those a human can solve easily but computers can't (having a conversation).
So this problem seems to fall into the later category, no? As a human, I can tell which program will loop forever, and which will stop after 10. But computers can't determine this.
So, back to Turing - would this not be a more effective test of "intelligence" than that silly competition people enter their chat bots into each year?
posted by Jimbob at 2:30 AM on November 26, 2008
This page, linked to in the post, list three programs. One loops a set number of times, one loops a number of times depending on the input, and the last loops forever.
As a human, I can look at these programs an immediately determine which program will do what. I seem to recall that people who are into the theoretical side of this stuff classify problems into those a computer can solve easily but human brains can't (crazy big arithmetic), and those a human can solve easily but computers can't (having a conversation).
So this problem seems to fall into the later category, no? As a human, I can tell which program will loop forever, and which will stop after 10. But computers can't determine this.
So, back to Turing - would this not be a more effective test of "intelligence" than that silly competition people enter their chat bots into each year?
posted by Jimbob at 2:30 AM on November 26, 2008
The problem is that if you find the answer to the halting problem, the universe sudd
posted by eriko at 2:36 AM on November 26, 2008 [6 favorites]
posted by eriko at 2:36 AM on November 26, 2008 [6 favorites]
As a human, I can tell which program will loop forever, and which will stop after 10. But computers can't determine this.
Sure, they can, for limited cases like that. But the solution for the limited cases won't work for every possible program, and you won't be able to tell any easier.
posted by grouse at 2:37 AM on November 26, 2008 [1 favorite]
Sure, they can, for limited cases like that. But the solution for the limited cases won't work for every possible program, and you won't be able to tell any easier.
posted by grouse at 2:37 AM on November 26, 2008 [1 favorite]
Jimbob: you're probably referring to NP Complete or a similar complexity class. Briefly (the wikipedia articles are good in general if you want more) a P problem takes twice, maybe three times as long to complete if you double the inputs. An NP problem might take ten or a hundred times longer after doubling the inputs.
I was tempted to bid $10,000 and take six months to deliver:
I was tempted to bid $10,000 and take six months to deliver:
#!/bin/sh # Consider the heat death of the universe a "completed" state exit 0;posted by Skorgu at 2:42 AM on November 26, 2008 [2 favorites]
I want to participate in some way, but this is already perfect.
posted by Bokononist at 3:42 AM on November 26, 2008
posted by Bokononist at 3:42 AM on November 26, 2008
Coincidentally Joel Spolsky's last podcast has a reasonably entertaining discussion on NP completeness and the halting problem, in which this xkcd is brought up.
posted by cillit bang at 3:53 AM on November 26, 2008
posted by cillit bang at 3:53 AM on November 26, 2008
exit 0;
Speaking of return codes, here's my shell script zen question.
What should false(1) return if it crashes?
posted by eriko at 4:07 AM on November 26, 2008
Speaking of return codes, here's my shell script zen question.
What should false(1) return if it crashes?
posted by eriko at 4:07 AM on November 26, 2008
What should false(1) return if it crashes?Mu!
posted by krilli at 4:36 AM on November 26, 2008 [2 favorites]
What should false(1) return if it crashes?
As it is written in the POSIX specification:
Regardless, the
posted by blasdelf at 4:42 AM on November 26, 2008 [5 favorites]
As it is written in the POSIX specification:
DESCRIPTION The false utility shall return with a non-zero exit code. EXIT STATUS The false utility shall always exit with a value other than zero. CONSEQUENCES OF ERRORS Default.Of greater concern is what
true could return:DESCRIPTION The true utility shall return with exit code zero. EXIT STATUS Zero. CONSEQUENCES OF ERRORS None.THE HORROR!
Regardless, the
false bourne shell built-in function does not parse it's arguments. Though the false included in the GNU coreutils is hilariously stupid — it has --help and --version arguments, and for some reason is not identical to true — even it doesn't take a real argument. Furthermore, "false(1)" would really be a call to run a function/program literally named "false(1)", which I suppose could really do whatever it wants to!posted by blasdelf at 4:42 AM on November 26, 2008 [5 favorites]
Currently the job posting is a silly prank.
But if the guy who posted it is logging the account names of the respondents to filter the responses he gets for any future job posts, he'll be ahead of the game.
posted by ardgedee at 5:10 AM on November 26, 2008 [2 favorites]
But if the guy who posted it is logging the account names of the respondents to filter the responses he gets for any future job posts, he'll be ahead of the game.
posted by ardgedee at 5:10 AM on November 26, 2008 [2 favorites]
Also guys? In the general cases, NP-hard problems are 'only' intractable, but the Halting Problem is fundamentally undecidable. Big difference.
The undecidability of the Halting Problem is one of the implications of Gödel's incompleteness theorems, which form a hard limit on what can be reasoned about, a bound on what truths can be known. To me, this result proves that idealism is unwarranted in this universe.
Problems in NP are just motherfucking hard, always get more complex exponentially (or worse), and are reducible to one another in polynomial time — they are a foil for clever people to bargain with: to try to cheat.
The two problem sets are not on the same level, or even really related.
posted by blasdelf at 5:28 AM on November 26, 2008 [2 favorites]
The undecidability of the Halting Problem is one of the implications of Gödel's incompleteness theorems, which form a hard limit on what can be reasoned about, a bound on what truths can be known. To me, this result proves that idealism is unwarranted in this universe.
Problems in NP are just motherfucking hard, always get more complex exponentially (or worse), and are reducible to one another in polynomial time — they are a foil for clever people to bargain with: to try to cheat.
The two problem sets are not on the same level, or even really related.
posted by blasdelf at 5:28 AM on November 26, 2008 [2 favorites]
(btw, the xkcd joke I posted fails by virtue of being easily solvable by brute force. You only need check 538 combinations, of which there are two answers: 7 mixed fruits; or 1 mixed fruit, 2 hot wings and 1 sampler plate)
posted by cillit bang at 5:32 AM on November 26, 2008 [1 favorite]
posted by cillit bang at 5:32 AM on November 26, 2008 [1 favorite]
it's clear the entire thing is a joke, right? or is the joke on me?
posted by spicynuts at 5:36 AM on November 26, 2008
posted by spicynuts at 5:36 AM on November 26, 2008
The answer is that determining whether a given piece of code will ever be executed it's isomorphic to the stopping problem.
Proof: insert a halt in the middle of that piece of code. Will the program execute the halt?
Funny, but actually I did "solve" this problem once.
It's the difference between being impossible in theory but possible in practice because of certain practical constraints. The real Halting Problem has infinite inputs (which is what makes it impossible to predict what might eventually happen if you wait long enough). In the real world, for certain classes of programs anyway, you are only going to get input from a finite set. You could test the whole set or certain representative elements and then have some reasonable level of assurance that you were covered.
Furthermore, you can probably still do something with certain cases. For instance, the chunk of code in question is not called from anywhere else in the code and is not an API. Status: Dead. Or perhaps the chunk deals with input that can be proved never to arrive due to some external constraint (negative body weights, say). If these constraints could be modeled, then a dead code finder could work in the specific class of programs that those constraints applied to.
I come across problems like this all the time at work. As a software engineer working for a researchish scientist, the tension between theory and practice is often present. Ironically, I'm usually the one that throws up my hands with a cry that such and such a problem is insoluble. Then the scientist comes up with a bunch of heuristics that solve 90-99% of the problem. Lesson: Just because there's no general solution doesn't mean you are completely screwed.
posted by DU at 5:40 AM on November 26, 2008 [3 favorites]
Proof: insert a halt in the middle of that piece of code. Will the program execute the halt?
Funny, but actually I did "solve" this problem once.
It's the difference between being impossible in theory but possible in practice because of certain practical constraints. The real Halting Problem has infinite inputs (which is what makes it impossible to predict what might eventually happen if you wait long enough). In the real world, for certain classes of programs anyway, you are only going to get input from a finite set. You could test the whole set or certain representative elements and then have some reasonable level of assurance that you were covered.
Furthermore, you can probably still do something with certain cases. For instance, the chunk of code in question is not called from anywhere else in the code and is not an API. Status: Dead. Or perhaps the chunk deals with input that can be proved never to arrive due to some external constraint (negative body weights, say). If these constraints could be modeled, then a dead code finder could work in the specific class of programs that those constraints applied to.
I come across problems like this all the time at work. As a software engineer working for a researchish scientist, the tension between theory and practice is often present. Ironically, I'm usually the one that throws up my hands with a cry that such and such a problem is insoluble. Then the scientist comes up with a bunch of heuristics that solve 90-99% of the problem. Lesson: Just because there's no general solution doesn't mean you are completely screwed.
posted by DU at 5:40 AM on November 26, 2008 [3 favorites]
So, here's a sketch of why you can't write a general program to tell whether a program halts.
Imagine you have such a program, H, that tells whether any program will eventually stop. By 'any program' I mean any program, including H or programs that call H. So, write another program called C that stops if a program given to H doesn't stop, but doesn't stop if a program given to H stop. What happens when C is asked whether C itself will stop? If H says it stops, it won't stop. If H says it won't stop, it stops. So we have a contradiction, yes? And so, in general, we can't write a program the that tells whether any program will eventually stop.
posted by willF at 5:43 AM on November 26, 2008 [7 favorites]
Imagine you have such a program, H, that tells whether any program will eventually stop. By 'any program' I mean any program, including H or programs that call H. So, write another program called C that stops if a program given to H doesn't stop, but doesn't stop if a program given to H stop. What happens when C is asked whether C itself will stop? If H says it stops, it won't stop. If H says it won't stop, it stops. So we have a contradiction, yes? And so, in general, we can't write a program the that tells whether any program will eventually stop.
posted by willF at 5:43 AM on November 26, 2008 [7 favorites]
cillit bang: (btw, the xkcd joke I posted fails by virtue of being easily solvable by brute force…)
No, it doesn't fail at all!
Problems in NP can only be conclusively solved in the general case by brute-force methods, by definition. They have a test that can take a reasonable (polynomial) amount of time, but since you have to apply the test to (nearly) all of the possible solutions, the whole problem can only be solved in polynomial time by using MAGIC NONDETERMINISM.
posted by blasdelf at 6:07 AM on November 26, 2008
No, it doesn't fail at all!
Problems in NP can only be conclusively solved in the general case by brute-force methods, by definition. They have a test that can take a reasonable (polynomial) amount of time, but since you have to apply the test to (nearly) all of the possible solutions, the whole problem can only be solved in polynomial time by using MAGIC NONDETERMINISM.
posted by blasdelf at 6:07 AM on November 26, 2008
Yeah, the common "but it's easy for any any person" argument is often made when first discussing the Halting Problem, but there are lots of examples of simple algorithms (such as Ackermann) where its actually incredibly difficult for a human to work out the answer.
As DU and delmoi have pointed out, the halting problem can have its importance overstated. There are many programs which you can conclusively prove terminate or don't. Its really not my field of computer science, but I suggest anyone interested check out Byron cook's page at Microsoft Research. When you start reducing the definition of what you call an algorithm, the problem becomes much more solvable in general.
posted by iso_bars at 6:41 AM on November 26, 2008 [1 favorite]
As DU and delmoi have pointed out, the halting problem can have its importance overstated. There are many programs which you can conclusively prove terminate or don't. Its really not my field of computer science, but I suggest anyone interested check out Byron cook's page at Microsoft Research. When you start reducing the definition of what you call an algorithm, the problem becomes much more solvable in general.
posted by iso_bars at 6:41 AM on November 26, 2008 [1 favorite]
thorough documentation and code commenting
What are those?
posted by oaf at 6:50 AM on November 26, 2008
What are those?
posted by oaf at 6:50 AM on November 26, 2008
darn, seems as though all the amusing bids are gone or am I just looking in the wrong place? anyone have it cache link?
posted by fatbaq at 6:56 AM on November 26, 2008
posted by fatbaq at 6:56 AM on November 26, 2008
DU: The halting problem is undecidable even with finite (or no) input to the program. Constraining the space available trivializes the problem somewhat, but not in a way that is particularly useful.
The fundamental conceit of the Halting Problem is that in order to know whether a program¹ returns you have to run it in some sense, and if it doesn't halt how the fuck are you really going to know? Limiting the number of possible programs doesn't help if you still have to effectively run all of them first before knowing conclusively whether they halt or not — you don't get static analysis for free.
The Entscheidungsproblem that Turing & Chuch solved was not originally posed about whether programs can be determined to return, but rather what they return — it was about whether well-formed mathematical expressions² can always be evaluated as to their truth. The negative result is a major bummer: we can't determine all of what is true in any language expressive enough to be worth using — we can't even prove that such a language contains no contradictions!. Plenty of logicians abandoned their careers over less immediately depressing (but often orthogonal) results.
¹In a turing-complete language
²In a theory capable of recursively expressing the natural numbers, equivalent to turing-completeness
posted by blasdelf at 6:57 AM on November 26, 2008
The fundamental conceit of the Halting Problem is that in order to know whether a program¹ returns you have to run it in some sense, and if it doesn't halt how the fuck are you really going to know? Limiting the number of possible programs doesn't help if you still have to effectively run all of them first before knowing conclusively whether they halt or not — you don't get static analysis for free.
The Entscheidungsproblem that Turing & Chuch solved was not originally posed about whether programs can be determined to return, but rather what they return — it was about whether well-formed mathematical expressions² can always be evaluated as to their truth. The negative result is a major bummer: we can't determine all of what is true in any language expressive enough to be worth using — we can't even prove that such a language contains no contradictions!. Plenty of logicians abandoned their careers over less immediately depressing (but often orthogonal) results.
¹In a turing-complete language
²In a theory capable of recursively expressing the natural numbers, equivalent to turing-completeness
posted by blasdelf at 6:57 AM on November 26, 2008
They appear to have deleted all of the project bids; did anyone catch a copy of them before they went away?
All I'm seeing now is a post on the messageboard from someone who is simply outraged that the project creator is not actually Alan Turing.
posted by ook at 6:59 AM on November 26, 2008
All I'm seeing now is a post on the messageboard from someone who is simply outraged that the project creator is not actually Alan Turing.
posted by ook at 6:59 AM on November 26, 2008
As a math-challenged English major who just finished Cryptonomicon, I approve of this thread.
posted by bardic at 7:05 AM on November 26, 2008
posted by bardic at 7:05 AM on November 26, 2008
> it's clear the entire thing is a joke, right? or is the joke on me?
Even though orthogonality provided the explanatory links, there's not enough context to understand why you should click 'em unless you don't need the explanatory links. So it's a bit of an acrostic to those not in the know. If you've read the thread this far, though, you ought to be able to suss out what's going on.
posted by ardgedee at 7:07 AM on November 26, 2008
Even though orthogonality provided the explanatory links, there's not enough context to understand why you should click 'em unless you don't need the explanatory links. So it's a bit of an acrostic to those not in the know. If you've read the thread this far, though, you ought to be able to suss out what's going on.
posted by ardgedee at 7:07 AM on November 26, 2008
OK, I need coffee before I can read this thread. I was a sociology major FFS.
posted by desjardins at 7:22 AM on November 26, 2008
posted by desjardins at 7:22 AM on November 26, 2008
I've archived the old unmoderated page for posterity's sake
posted by blasdelf at 7:33 AM on November 26, 2008 [7 favorites]
posted by blasdelf at 7:33 AM on November 26, 2008 [7 favorites]
Problems in NP can only be conclusively solved in the general case by brute-force methods, by definition. They have a test that can take a reasonable (polynomial) amount of time, but since you have to apply the test to (nearly) all of the possible solutions, the whole problem can only be solved in polynomial time by using MAGIC NONDETERMINISM.
You're assuming P != NP, which last I checked was a major open problem, not a trivial fact you can snark about.
posted by grobstein at 7:39 AM on November 26, 2008 [4 favorites]
You're assuming P != NP, which last I checked was a major open problem, not a trivial fact you can snark about.
posted by grobstein at 7:39 AM on November 26, 2008 [4 favorites]
Google cache still has the bids from before they got erased, and I have also mirrored it...
I did not get the CS reference without the supplementary links (as I dd not study CS) but could see that the problem was impossible to solve -- as someone above menitioned, its like asking for the computing version of a perpetual motion machine... So it was amusing reading the very eager bids from real people/companies who had no idea what was being asked of them... (and as a consutant programmer, scary to see how cheaply some people were pricing themselves!)
I don't normally make fun of people's engrish, but:
"give us the opportunity to arise up your needs to be done"
Aaah memories of Zero Wing :)
posted by nielm at 7:49 AM on November 26, 2008 [1 favorite]
I did not get the CS reference without the supplementary links (as I dd not study CS) but could see that the problem was impossible to solve -- as someone above menitioned, its like asking for the computing version of a perpetual motion machine... So it was amusing reading the very eager bids from real people/companies who had no idea what was being asked of them... (and as a consutant programmer, scary to see how cheaply some people were pricing themselves!)
I don't normally make fun of people's engrish, but:
"give us the opportunity to arise up your needs to be done"
Aaah memories of Zero Wing :)
posted by nielm at 7:49 AM on November 26, 2008 [1 favorite]
To elaborate, NP problems are problems that can be solved in polynomial time by a non-deterministic Turing machine (a model of computing that we can't simulate efficiently and generally, but not "MAGIC," in the sense that its properties are defined in precise mathematics). Because of the power of the NTM model, the easiest general solution that shows a problem is in NP is usually a brute-force search. In many cases, the best known solution is a brute-force search. But this doesn't mean that the best general solution for any NP problem is a brute-force search, or close to a brute force search. If a single such problem were discovered, we would know P != NP. (Background.)
emphasis in my last post was supplied by me and not in the original quote; I highlighted the thing that we don't actually know
posted by grobstein at 7:59 AM on November 26, 2008
emphasis in my last post was supplied by me and not in the original quote; I highlighted the thing that we don't actually know
posted by grobstein at 7:59 AM on November 26, 2008
Incidentally if you're sitting on the solution, you shouldn't, because it's worth a $1m prize, and probably a Fields Medal, tenure at a top school, and some other goodies.
posted by grobstein at 8:01 AM on November 26, 2008 [2 favorites]
posted by grobstein at 8:01 AM on November 26, 2008 [2 favorites]
Just to prove I am a programmer, but not a computer scientist, I wrote a program to solve the xkcd script. Using brute force. The way real men solve problems.
posted by Jimbob at 9:02 AM on November 26, 2008
posted by Jimbob at 9:02 AM on November 26, 2008
"I did not get the CS reference without the supplementary links (as I dd not study CS) but could see that the problem was impossible to solve"
Just by looking at it with no previous computer science experience? Can you quickly peruse the US Constitution and see if there are any inconsistencies that could lead to a dictatorship?
This is going to be a thread of annoying CSCI insider jokes, ain't it?
posted by bonecrusher at 9:06 AM on November 26, 2008 [2 favorites]
Just by looking at it with no previous computer science experience? Can you quickly peruse the US Constitution and see if there are any inconsistencies that could lead to a dictatorship?
This is going to be a thread of annoying CSCI insider jokes, ain't it?
posted by bonecrusher at 9:06 AM on November 26, 2008 [2 favorites]
Yes, I believe and assume P ≠ NP, but I don't believe a proof of that is possible.
Actually, I think a proof of P = NP is more likely than a proof to the contrary, but I only see two astonishingly unlikely methods to prove P = NP:
posted by blasdelf at 9:20 AM on November 26, 2008
Actually, I think a proof of P = NP is more likely than a proof to the contrary, but I only see two astonishingly unlikely methods to prove P = NP:
- Implement a natively nondeterministic model for computation in our universe.
- Prove that NP=NP-complete, and write a P-time algorithm for a NP problem.
posted by blasdelf at 9:20 AM on November 26, 2008
nielm and blasdelf, thank you!
The non-joke bids are going to be a great reference when I next need to explain to someone why these rentacoder sites are a waste of time. And the joke bids are awesome.
posted by ook at 9:28 AM on November 26, 2008
The non-joke bids are going to be a great reference when I next need to explain to someone why these rentacoder sites are a waste of time. And the joke bids are awesome.
posted by ook at 9:28 AM on November 26, 2008
If someone is taking cash bids on a "solution," positive results begin when that expense is exceeded by savings in a particular class of applications.
An example is the Intelligent Scissors image compositing tools in Photoshop and elsewhere (basically the traveling salesman problem, with a lot of cities, that needs to be real time interactive.)
The heuristics are very efficient and produce useful, usable results.
posted by StickyCarpet at 9:39 AM on November 26, 2008
An example is the Intelligent Scissors image compositing tools in Photoshop and elsewhere (basically the traveling salesman problem, with a lot of cities, that needs to be real time interactive.)
The heuristics are very efficient and produce useful, usable results.
posted by StickyCarpet at 9:39 AM on November 26, 2008
Why do programmers get Christmas and Halloween confused?
Because Oct 31 is Dec 25.
posted by East Manitoba Regional Junior Kabaddi Champion '94 at 10:06 AM on November 26, 2008 [2 favorites]
Because Oct 31 is Dec 25.
posted by East Manitoba Regional Junior Kabaddi Champion '94 at 10:06 AM on November 26, 2008 [2 favorites]
Why do programmers confuse Christmas with Halloween?
...
Because Oct 31 == Dec 25.
posted by Who_Am_I at 10:10 AM on November 26, 2008
...
Because Oct 31 == Dec 25.
posted by Who_Am_I at 10:10 AM on November 26, 2008
wtf EMRJKC'94
posted by Who_Am_I at 10:10 AM on November 26, 2008 [1 favorite]
posted by Who_Am_I at 10:10 AM on November 26, 2008 [1 favorite]
WHO ARE YOU!?
posted by East Manitoba Regional Junior Kabaddi Champion '94 at 10:26 AM on November 26, 2008 [2 favorites]
posted by East Manitoba Regional Junior Kabaddi Champion '94 at 10:26 AM on November 26, 2008 [2 favorites]
I get that this is a joke, but I'm curious. So it's impossible to construct a solution to this problem that works on all cases. But I don't see how this precludes a solution that works most of the time.
posted by limon at 10:59 AM on November 26, 2008
posted by limon at 10:59 AM on November 26, 2008
"I did not get the CS reference without the supplementary links (as I dd not study CS) but could see that the problem was impossible to solve"
Just by looking at it with no previous computer science experience?
I did state that I was a programmer, I just didn't study CS theory at uni, so do not know the math that is behind problems like these.
Anyway there are certain things are fairly self-evident with some small thought, but even then they can take significant proof ... (eg perpetual motion machines or 1+1=2)
As for the US consitution... I am not a political scientist, have not studied the consitution and so can not prove anything. However it is often said that the constitution is a living/evolving document. Therefore if it can be changed at all, it can theoretically be changed to allow anything...
posted by nielm at 11:04 AM on November 26, 2008
Just by looking at it with no previous computer science experience?
I did state that I was a programmer, I just didn't study CS theory at uni, so do not know the math that is behind problems like these.
Anyway there are certain things are fairly self-evident with some small thought, but even then they can take significant proof ... (eg perpetual motion machines or 1+1=2)
As for the US consitution... I am not a political scientist, have not studied the consitution and so can not prove anything. However it is often said that the constitution is a living/evolving document. Therefore if it can be changed at all, it can theoretically be changed to allow anything...
posted by nielm at 11:04 AM on November 26, 2008
Bug finding program:
This output is guaranteed to be correct when the input was written by mortals for execution by mortals on hardware designed by mortals. Testing has met with some obstacles for the other cases.
Oh, you wanted it to tell you where the bugs are? Sorry, that's gonna cost you hourly.
posted by eritain at 11:04 AM on November 26, 2008 [3 favorites]
print "Bugs found\n";This output is guaranteed to be correct when the input was written by mortals for execution by mortals on hardware designed by mortals. Testing has met with some obstacles for the other cases.
Oh, you wanted it to tell you where the bugs are? Sorry, that's gonna cost you hourly.
posted by eritain at 11:04 AM on November 26, 2008 [3 favorites]
What do you hold out more hope for?
I tend to suspect along with you that P != NP, though I don't think I share your view about the relative difficulties of proof. But I don't think of it as a foregone conclusion, given especially my own ignorance but also my sense that the study of algorithms is still fairly open and my knowledge that we're still learning weird things like that Primes is in P -- the test is not very efficient, and somewhat gnarly, but at least suggests that the intuitive force of the argument that some problem is not in P can be misleading.
posted by grobstein at 11:12 AM on November 26, 2008
I tend to suspect along with you that P != NP, though I don't think I share your view about the relative difficulties of proof. But I don't think of it as a foregone conclusion, given especially my own ignorance but also my sense that the study of algorithms is still fairly open and my knowledge that we're still learning weird things like that Primes is in P -- the test is not very efficient, and somewhat gnarly, but at least suggests that the intuitive force of the argument that some problem is not in P can be misleading.
posted by grobstein at 11:12 AM on November 26, 2008
Sorry nielm - re-reading what I wrote, it sounds more dickish than I meant it to.
The constitution bit is from this:
On December 5, 1947, Einstein and Morgenstern accompanied Gödel to his U.S. citizenship exam, where they acted as witnesses. Gödel had confided in them that he had discovered an inconsistency in the U.S. Constitution, one that would allow the U.S. to become a dictatorship.
posted by bonecrusher at 11:17 AM on November 26, 2008
The constitution bit is from this:
On December 5, 1947, Einstein and Morgenstern accompanied Gödel to his U.S. citizenship exam, where they acted as witnesses. Gödel had confided in them that he had discovered an inconsistency in the U.S. Constitution, one that would allow the U.S. to become a dictatorship.
posted by bonecrusher at 11:17 AM on November 26, 2008
But I don't see how this precludes a solution that works most of the time.
As others have said upthread, it doesn't. The joke is mostly about the fact that so many clueless people will bid for any random project, rather than that no project like this could ever be useful.
A similar joke posting on a rentacoder-like site a few years ago said something along the lines of "Write a new OS from scratch (no open source code), that is similar to Unix but can run any Windows application." Of course such a project would be a challenge for Microsoft themselves, but plenty of scrappy dev teams submitted bids.
posted by burnmp3s at 11:18 AM on November 26, 2008
As others have said upthread, it doesn't. The joke is mostly about the fact that so many clueless people will bid for any random project, rather than that no project like this could ever be useful.
A similar joke posting on a rentacoder-like site a few years ago said something along the lines of "Write a new OS from scratch (no open source code), that is similar to Unix but can run any Windows application." Of course such a project would be a challenge for Microsoft themselves, but plenty of scrappy dev teams submitted bids.
posted by burnmp3s at 11:18 AM on November 26, 2008
Can you quickly peruse the US Constitution and see if there are any inconsistencies that could lead to a dictatorship?
This was a joke about Godel's naturalization hearing, right? Here's the best discussion I've found.
Peter Suber thinks the "inconsistency" is the possibility of amending everything, including the Amendments Clause. I have a friend who floated the idea that the President could appoint himself to the Supreme Court.
on preview, bonecrusher has explained himself. but for those still curious after the tiny wikipedia treatment, I'm posting this anyway.
posted by grobstein at 11:36 AM on November 26, 2008 [1 favorite]
This was a joke about Godel's naturalization hearing, right? Here's the best discussion I've found.
Peter Suber thinks the "inconsistency" is the possibility of amending everything, including the Amendments Clause. I have a friend who floated the idea that the President could appoint himself to the Supreme Court.
on preview, bonecrusher has explained himself. but for those still curious after the tiny wikipedia treatment, I'm posting this anyway.
posted by grobstein at 11:36 AM on November 26, 2008 [1 favorite]
A similar joke posting on a rentacoder-like site a few years ago said something along the lines of "Write a new OS from scratch (no open source code), that is similar to Unix but can run any Windows application." Of course such a project would be a challenge for Microsoft themselves, but plenty of scrappy dev teams submitted bids.
It also arguably runs afoul of Rice's Theorem, a kind of corollary of the halting problem theorem. Rice's Theorem says there's no general method of determining whether a given program will run under Windows i think, so arguably the set of "Windows applications" is not well-defined.
posted by grobstein at 11:41 AM on November 26, 2008
It also arguably runs afoul of Rice's Theorem, a kind of corollary of the halting problem theorem. Rice's Theorem says there's no general method of determining whether a given program will run under Windows i think, so arguably the set of "Windows applications" is not well-defined.
posted by grobstein at 11:41 AM on November 26, 2008
Nice link grobstien (the only thing more awesome than Jim Holt is Lingua Franca). Leiter had a discussion of this issue once on his blog.
posted by bonecrusher at 12:14 PM on November 26, 2008
posted by bonecrusher at 12:14 PM on November 26, 2008
grobstein writes "Can you quickly peruse the US Constitution and see if there are any inconsistencies that could lead to a dictatorship?
"This was a joke about Godel's naturalization hearing, right? Here's the best discussion I've found.
"Peter Suber thinks the 'inconsistency' is the possibility of amending everything, including the Amendments Clause. I have a friend who floated the idea that the President could appoint himself to the Supreme Court.
Thank you, grobstein! I've been wondering about that story for years.
posted by Araucaria at 12:32 PM on November 26, 2008
"This was a joke about Godel's naturalization hearing, right? Here's the best discussion I've found.
"Peter Suber thinks the 'inconsistency' is the possibility of amending everything, including the Amendments Clause. I have a friend who floated the idea that the President could appoint himself to the Supreme Court.
Thank you, grobstein! I've been wondering about that story for years.
posted by Araucaria at 12:32 PM on November 26, 2008
bonecrusher - no worries - of course the reference to Godel and the constitution completely flew past me, but interesting links from you and grobstein...
Do I get the points for (approximately) the right answer though :)
Reading the computing theory articles on wikipedia makes my head hurt...
posted by nielm at 12:40 PM on November 26, 2008
Do I get the points for (approximately) the right answer though :)
Reading the computing theory articles on wikipedia makes my head hurt...
posted by nielm at 12:40 PM on November 26, 2008
You get points for the most plausible charitable answer, nielm. I'm pretty sure the right answer is "Godel was really, really crazy." Dude basically starved himself to death.
Back in my college days, my logic professor used to begin each class by handing out a xeroxed headshot of a famous logician and then describe his mental illness.
posted by bonecrusher at 1:20 PM on November 26, 2008 [1 favorite]
Back in my college days, my logic professor used to begin each class by handing out a xeroxed headshot of a famous logician and then describe his mental illness.
posted by bonecrusher at 1:20 PM on November 26, 2008 [1 favorite]
Back in my college days, my logic professor used to begin each class by handing out a xeroxed headshot of a famous logician and then describe his mental illness.
I had a prof who did this! . . . not every day, though. Godel did look creepy in his age -- like a lemur.
posted by grobstein at 1:27 PM on November 26, 2008
I had a prof who did this! . . . not every day, though. Godel did look creepy in his age -- like a lemur.
posted by grobstein at 1:27 PM on November 26, 2008
grobstein - University of Minnesota? Anderson was his name, I think. This was nearly 20 years ago, so my memory isn't the greatest.
posted by bonecrusher at 4:29 PM on November 26, 2008
posted by bonecrusher at 4:29 PM on November 26, 2008
Purify is an excellent bug finding program, and I have had plenty success with Coverity as well.
But that that is relevant to the original FFP.
posted by lundman at 7:22 PM on November 26, 2008
But that that is relevant to the original FFP.
posted by lundman at 7:22 PM on November 26, 2008
The comment board is funny
germanquality
Frankfurt, DElocation US$300 bid amount
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.
posted by MiltonRandKalman at 8:30 PM on November 26, 2008
germanquality
Frankfurt, DElocation US$300 bid amount
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.
posted by MiltonRandKalman at 8:30 PM on November 26, 2008
"Scooping the Loop Snooper" is an alternative proof of the halting problem's undecidability, Dr. Seuss-style.
posted by teraflop at 8:55 PM on November 26, 2008 [2 favorites]
posted by teraflop at 8:55 PM on November 26, 2008 [2 favorites]
Someone one asked me if we could automate the detection of duplicate bugs in our bug tracker.
posted by RobotVoodooPower at 5:38 AM on November 27, 2008
posted by RobotVoodooPower at 5:38 AM on November 27, 2008
grobstein - Primality checking is in P? Cool. I missed that.
posted by Pronoiac at 12:36 PM on December 8, 2008
posted by Pronoiac at 12:36 PM on December 8, 2008
I was going to send this to a friend of mine, but was dismayed to find that all the bids seem to have been removed. Looks like the getacoder.com people don't have a sense of humor.
posted by grouse at 10:29 PM on December 10, 2008
posted by grouse at 10:29 PM on December 10, 2008
grobstein: Yes. At least factorization is still open. At least, I seriously hope so. Okay, this is my nervous look.
grouse: A couple of mirrors are linked above.
posted by Pronoiac at 10:17 AM on December 11, 2008 [1 favorite]
grouse: A couple of mirrors are linked above.
posted by Pronoiac at 10:17 AM on December 11, 2008 [1 favorite]
« Older Up in the sky! | Dufaycolour, Technicolor and Kodachrome Newer »
This thread has been archived and is closed to new comments
posted by Class Goat at 12:25 AM on November 26, 2008