You aren't attempting to elicit knowledge or image recognition from the human, you are attempting to elicit emotion.
Of course you are. You're eliciting a piece of information, a description of an emotion. This response is made up of bytes and is subject to all the same rules that any other response is.
As for training -- how do you plan to train the image classifier in the first place? Either it's manual or automatic, and the points I made in my first post still apply. Making the classifier self-training actually makes the system worse because as soon as an attacker starts scoring hits, the system modifies itself to fit the attacker's responses -- which it now identifies as human.
The entire system of how email works right now needs to be thrown away.
It's worse than that. Any free or recipient-pays message system is subject to exactly the same amount of abuse. When sending a message costs nothing, the marginal cost of advertising is zero. As long as the marginal gain is non-zero, however small, volume will go to infinity. You can filter and legislate to reduce the volume of this advertising, but you'll never actually eliminate it. These countermeasures just bring the marginal cost of email up to slightly above zero --- but not nearly high enough to discourage spam.
Email isn't special. SMTP is fine. There was fax-machine spam long before even Compuserve. Today, we see text message spam, Facebook spam, MySpace spam, and so on. Email itself isn't the problem. Changing what you call the system doesn't change how it works. It's recipient-pays messaging that's the problem.
Sure, sender-pay systems like the postal service see some volume of advertising, but the volume is kept down by the relatively high marginal cost. Ultimately, I don't see a way of reconciling free anonymous messaging with a spam-free inbox.
You can't think about the problem in terms of what the user sees. Instead, you have to think about it in terms of the information that's sent over the wire, because that's all the good guy's server has to go on. The server sets a set of images and receives a set of keywordimage associations in reply. How is the server supposed to know which keywords go with which images? Either some operator entered that information beforehand, or the server used an algorithm to assign keywords to images. In the first case, the set of images is small, and an attacker could just as easily enter the same information. In the second case, an attacker could simply run the same algorithm on the images he receives and send the results back to the server. Image-label CAPTCHA approaches are doomed. DOOMED. Why?
Let's say Bob is running a webmail service and Dimitri is writing Craigslist posting software that needs fresh email-addresses. Dimitri only needs 5% of his email account registration attempts to succeed. If Bob is using the image-label CAPTCHA approach, he needs to put in 20 times the effort into labeling images as Dimitri is putting into them labeling images; less, in fact, since it's less expensive for Dimitri to label images than it is for Bob to find and label them.
Your CAPTCHA is trivially cracked. Luckily for you, it's not worth a spammer's time to crack even that pathetic CAPTCHA, and so you don't get any spam. Now, try running a webmail service and see how long that lasts.
The point is that there are many solutions that work for smaller sites that simply do not stand up to concentrated attack. Webmail providers are especially vulnerable because throwaway email addresses enable many other kinds of malfeasance. Really, the problem we're talking about here isn't protecting your comment box. It's protecting large services against concentrated attack, and that's a much harder problem.
The problem is that CAs are subject to the "too big to fail" problem. Consider the Comodo certificate debacle -- Comodo delegated the authority to grant certificates to a third-party reseller, CertStar. CertStar then issued a certificate for mozilla.com with no validation whatsoever. This is about as big a breach of trust as a CA can manage short of publicly posting its master private key on a web page in China.
What happened? Fucking nothing happened. Sure, CertStar's wrist was slapped, and Comodo made a bunch of promises, but there were no reprisals, and no consequences. The Mozilla people refused to revoke the Comodo certificate because it would "break the web", and too many websites would stop working mysteriously.
What was the end result? Moral hazard for certificate authorities, and danger for users. My point is that CAs aren't fairies who are always magically correct. They're as vulnerable to incompetence and corruption as any institution.
(P.S.: I disable Comodo certificates in all browsers I use. I suggest you do the same thing.)
Speech recognition is much harder than image pattern recognition. Mainly because our human brain can easily parse accents and sloppy speaking, computers hardly can.
You fool -- what do you think our brains are except massively parallel computers? There's no conceptual barrier to better speech recognition. The problem is the same as image recognition, really, with one axis of a 2D image replaced with the time dimension of the recording. The arguments and counter-arguments that apply to image captchas also apply to audio ones just as well.
Audio catpcha crackers don't need to write dictation programs. Audio captchas as limited: you can't distort the signal too much: someone speaking in a thick Irish brogue will confuse many listeners. Words can't be particularly unfamiliar. The objects to be recognized must be familiar -- just as you can't expect random blog posters to type, say, Ancient Phoenician symbols into your captcha, you don't want to limit your posters to people with SAT verbal scores about 700 (however desirable a side-effect that might be).
While audio captchas might be effective for a little while, crackers will eventually figure out how to crack them, and we'll end up in the same place we are today. It's a classic Red Queen effect.
A CAPTCHA is not a Turing test. A Turing test requires that a person tell a computer and a human apart; the CAPTCHA problem is harder, from a certain point of view, because a computer is required to tell a human and a computer apart.
Everyone has a great idea for a CAPTCHA, but very few people know what the hell is really going on. Remember that the machine doesn't need to solve the CAPTCHA every time, that machines are infinitely patient and have huge memories, and that another machine needs to make sure the human gave the right answer!
Ideas that won't work:
Make clients identify an object from a picture. Machines can't describe objects in pictures: if machines can't describe the picture, how the hell is the CAPTCHA server supposed to verify that the client gave the correct answer? If a human being manually inputs the pictures and acceptable descriptions for each, then another human can program his attacking machine to do the same thing! Having a large, but finite set of pictures doesn't help either since a machine doesn't need to solve the CAPTCHA every time. It can just learn the correct responses without actually understanding the image. ANY APPROACH BASED ON IDENTIFYING A MEMBER OF A FINITE SET DOES NOT WORK AS A CAPTCHA.
As a special case of #2, QUIZZES DO NOT WORK: either the questions are finite and subject to attacker memorization, or the number of patterns for the question is finite, and these patterns can be detected by a machine. (Consider "A train is coming from Denver at X miles per hour..." --- same problem, different coefficients)
Send the client a special program that verifies he's real: if it doesn't work for DRM, it won't work for CAPTCHAs. An attacker can just program his machine to simulate slow typing, slow thinking, or a cross-eyed human being. YOU CANNOT CONTROL THE EXECUTION ENVIRONMENT. No amount of Javascript obfuscation, encryption, or header-checking will make the slightest bit of difference for a determined hacker.
As a special case of #3, TIMING ANALYSIS DOES NOT WORK. Machines can simulate arbitrary delays.
Limiting CAPTCHA-solving attempts by cookie/IP address/etc.: that doesn't work. Attackers don't obey web standards, and have botnets
Really, it's very easy to think you've come up with a very clever CAPTCHA. When you think that, all you've done is stoked your ego and screwed yourself over. It's the same reason why we don't roll our own cryptography: CAPTCHA-making is a very hard problem, mainly because your problem space must be infinite (to avoid an attacking machine simply memorizing answers), the answers verifiable by a machine, but the problems not solvable by a machine.
How many questions can be checked by machines but not answered by them?
Not many; fewer every day. There are no questions that can't be answered by a computer (and which can be answered by a human mind). The Church-Turing thesis [wikipedia.org] has some validity: the human mind is no more powerful than a turing machine, and ultimately, computers and our brains are equivalently computationally. There's nothing a computer can't solve: there are just things we haven't figured out yet.
First-world nations had plentyofproblems with their space programs at first too. Considering that North Korea has isolated itself, it's not surprising that they're going through the pain everyone else went through 60 years ago.
The universe can do things you can't. Inflation is a change in the scale of the universe, not the motion of some object within it. They're entirely different effects.
That jet only appears to be superluminal due to the relative motion of the solar system and the jet's source. It's not actually moving faster than light in its own reference frame. Also, Hawking radiation doesn't count: we're dealing with distances on the order of a Planck length, where speed becomes meaningless. You might as well say particles do the Macarena as say that they move faster than light.
We're not so sure that causality is a reflection of how our brain works or how the universe works.
A bit solipsistic are we? There is an objective universe out there, and it obeys laws of causality and logic without our being involved at all. To imagine otherwise is arrogance (especially if your name is Penrose.)
Sorry, but we already have faster-than-light communication trough quantum entanglement. The change in state happens instantly, without any delay, no matter what the distance is.
That doesn't work. You can't transmit information faster than light; contrary to popular conception, quantum entanglement does not involve classical information transfer.
If you have one of a pair of dice, and the other is a thousand light-years away, one way to think of entanglement is to imagine that whatever number you roll is the number that shows up on the other die the next time it is rolled. Even if the two dice are linked, you can't control which number shows up, so you can't use the dice to communicate information.
Faster-than-light travel always causes causality paradoxes, so a priori, FTL drives are impossible unless special relativity is wrong. (That's is a bit like saying that perpetual motion machines are impossible unless thermodynamics is wrong.) The proposed mechanism behind the FTL drive doesn't matter -- it'll still cause a time paradox.
Just like we know any proposed perpetual motion machine must have a flaw, any proposed FTL drive must also have a flaw. They belong to the same class of impossible device, and deserve the same degree of consideration.
Nifty. Stark's been in office since 1973, but he only announced his atheism in 2007. Though he got 78% of the vote in 2008, he had a huge advantage in name recognition. For the next step, let's try to get a non-incumbent atheist elected.
I believe that this resolution is aimed at least in part at secular attacks on religion. As Gandhi said, "first they ignore you, then they laugh at you, then they fight you, then you win."
We atheists have been given the short shrift for a very long time now. First we were burned at the stake, then persecuted, and now we're gradually gaining mainstream acceptance now. We've gone from Bush the Elder claiming that atheists should be considered neither citizens nor patriots to Obama including non-believers in his inauguration speech. Perhaps in my lifetime, it'll be politically feasible for an atheist to hold an elected office.
It's no wonder that the religious old guard is running scared.
You did not understand my post. The sentence you mock comes from a section dealing with the common proposal for using the image classification problem as a CAPTCHA. More formally, in the classification approach, you have pre-existing images I_1, I_2, I_i and so on up to I_N. N is finite. Each image has a label L_1, L_2, L_i,... L_N attached to it. The server sends the client a subset of the total set of images and asks for the corresponding labels (or equivalently, the server asks which images in the sent set have the given label attached.)
The trouble is that if N is small, it is possible to simply teach a malicious client about L_i for each i L. If such an algorithm exists, an attacker can use the same algorithm to generate the labels for the images the server sends as the challenge.
This discussion does not apply to the article's technique since the 3D captcha approach involved generated images; you're correct in that it's not amenable to a simple memorization attack. But as other posters have mentioned in this thread, 3D image recognition is essentially a solved problem algorithmically speaking, and it's only a matter of time before spammers learn to apply these algorithms in making their malicious clients.
If there's one pattern we see over and over again in CAPTCHA discussions, it's that an intuitive notion of what AI can do is flawed. You seem to think it's unlikely that a machine can recognize an arbitrarily-rotated 3D object, but they in fact can. Similar arguments apply to speech recognition, natural language parsing, route planning, and other tasks. Even if a particular problem doesn't yet have an algorithmic solution, it is only a matter before one is found: as the last part of my post indicated, the human mind is computationally equivalent to a Turing machine, and there is no problem that is fundamentally intractable for a computer that is not also fundamentally difficult for a human.
I must concede, however, that a Turing machine is merely an upper limit for the computational power of a human brain. As your post demonstrates, this limit gives some brains no trouble at all.
every time somebody adds a 3d object into their captcha, you would have to get enough sample images to train your classifier.
It's worse than that, actually. Remember, a machine doesn't need to pass the captcha every time. You only need to worry about re-training your image recognizer when the success rate falls below a useful level, and even very low levels of CAPTCHA success are useful for spammers.
Personally, I think the regular photographic captchas (i.e., "click on the Siamese cat") are a better idea.
Won't work. Where will you get your pictures of Siamese Cats? If you take them yourself, you'll only have a few. Spammers will simply train their bots to recognize these cats.
If you have lots of pictures of cat and non-cat objects, the attacker has two strategies: either he can get the same database you did (which you didn't make, because making a large enough database would be cost-prohibitive), or failing that, he just trains his image recognized to pick out characteristics of Siamese cats the same way a human brain would.
You know enough that recognizing 3D shapes is a solved problem; doesn't it seem clear that recognizing textures would be just as tractable?
And I imagine you could create tough cases, but these cases will also trip up human beings.
Before someone jumps in with "humans can solve the halting problem!" -- we really can't. There are problems that obviously halt, and programs that obviously don't. We can tell these apart, but so can computers. It's the complicated, borderline cases that trip up both people and computers.
Furthermore, there are important caveats to the halting problem: first, you can tell whether a program halts in a given time. You just run it and see whether it halts! Human beings do this all the time when debugging hanging programs. We use a good heuristic that says "if a program doesn't quit after a good long while, it probably won't quit at all." (And that holds in most cases.)
Second, the halting problem can be solved, via brute force if necessary, for a restricted-memory machine. Make the available memory size small enough and you can actually perform useful validation. The proof of the halting problems' unsolvability applies only to unrestricted turing machines.
A true turing machine has never been built, and can't exist in our universe. Every computer is a limited-memory approximation.
Everyone has a great idea for a CAPTCHA, but very few people know what the hell is really going on. Remember that the machine doesn't need to solve the CAPTCHA every time, that machines are infinitely patient and have huge memories, and that another machine needs to make sure the human gave the right answer!
Ideas that won't work:
Make clients identify an object from a picture. Machines can't describe objects in pictures: if machines can't describe the picture, how the hell is the CAPTCHA server supposed to verify that the client gave the correct answer? If a human being manually inputs the pictures and acceptable descriptions for each, then another human can program his attacking machine to do the same thing! Having a large, but finite set of pictures doesn't help either since a machine doesn't need to solve the CAPTCHA every time. It can just learn the correct responses without actually understanding the image. ANY APPROACH BASED ON IDENTIFYING A MEMBER OF A FINITE SET DOES NOT WORK AS A CAPTCHA.
As a special case of #2, QUIZZES DO NOT WORK: either the questions are finite and subject to attacker memorization, or the number of patterns for the question is finite, and these patterns can be detected by a machine. (Consider "A train is coming from Denver at X miles per hour..." --- same problem, different coefficients)
Send the client a special program that verifies he's real: if it doesn't work for DRM, it won't work for CAPTCHAs. An attacker can just program his machine to simulate slow typing, slow thinking, or a cross-eyed human being. YOU CANNOT CONTROL THE EXECUTION ENVIRONMENT. No amount of Javascript obfuscation, encryption, or header-checking will make the slightest bit of difference for a determined hacker.
As a special case of #3, TIMING ANALYSIS DOES NOT WORK. Machines can simulate arbitrary delays.
Limiting CAPTCHA-solving attempts by cookie/IP address/etc.: that doesn't work. Attackers don't obey web standards, and have botnets
Really, it's very easy to think you've come up with a very clever CAPTCHA. When you think that, all you've done is stoked your ego and screwed yourself over. It's the same reason why we don't roll our own cryptography: CAPTCHA-making is a very hard problem, mainly because your problem space must be infinite (to avoid an attacking machine simply memorizing answers), the answers verifiable by a machine, but the problems not solvable by a machine.
How many questions can be checked by machines but not answered by them?
Not many; fewer every day. There are no questions that can't be answered by a computer (and which can be answered by a human mind). The Church-Turing thesis has some validity: the human mind is no more powerful than a turing machine, and ultimately, computers and our brains are equivalently computationally. There's nothing a computer can't solve: there are just things we haven't figured out yet.
Please don't use tinyurl unnecessarily. You could have directly linked to the pages you mention. It's impossible to tell where the links go when you use tinyurl.
David Swensen and Michael Schmidt proposed that newspapers simply receive endowments and operate off the interest, insulating them from commercial pressures and conflicts of interest. I think that's a fantastic idea, especially in conjunction with legal nonprofit status for newspapers.
Slashdot Mirror
His kangaroo trial was conducted by Vichy Iraqis at our urging.
Besides -- if his trial didn't meet our standards, we should have condemned the result anyway. Principles don't have geographic boundaries.
Of course you are. You're eliciting a piece of information, a description of an emotion. This response is made up of bytes and is subject to all the same rules that any other response is.
As for training -- how do you plan to train the image classifier in the first place? Either it's manual or automatic, and the points I made in my first post still apply. Making the classifier self-training actually makes the system worse because as soon as an attacker starts scoring hits, the system modifies itself to fit the attacker's responses -- which it now identifies as human.
If you have the proper IEEE 754 exception disabled, the answer is positive infinity. :-)
It's worse than that. Any free or recipient-pays message system is subject to exactly the same amount of abuse. When sending a message costs nothing, the marginal cost of advertising is zero. As long as the marginal gain is non-zero, however small, volume will go to infinity. You can filter and legislate to reduce the volume of this advertising, but you'll never actually eliminate it. These countermeasures just bring the marginal cost of email up to slightly above zero --- but not nearly high enough to discourage spam.
Email isn't special. SMTP is fine. There was fax-machine spam long before even Compuserve. Today, we see text message spam, Facebook spam, MySpace spam, and so on. Email itself isn't the problem. Changing what you call the system doesn't change how it works. It's recipient-pays messaging that's the problem.
Sure, sender-pay systems like the postal service see some volume of advertising, but the volume is kept down by the relatively high marginal cost. Ultimately, I don't see a way of reconciling free anonymous messaging with a spam-free inbox.
You can't think about the problem in terms of what the user sees. Instead, you have to think about it in terms of the information that's sent over the wire, because that's all the good guy's server has to go on. The server sets a set of images and receives a set of keywordimage associations in reply. How is the server supposed to know which keywords go with which images? Either some operator entered that information beforehand, or the server used an algorithm to assign keywords to images. In the first case, the set of images is small, and an attacker could just as easily enter the same information. In the second case, an attacker could simply run the same algorithm on the images he receives and send the results back to the server. Image-label CAPTCHA approaches are doomed. DOOMED. Why?
Let's say Bob is running a webmail service and Dimitri is writing Craigslist posting software that needs fresh email-addresses. Dimitri only needs 5% of his email account registration attempts to succeed. If Bob is using the image-label CAPTCHA approach, he needs to put in 20 times the effort into labeling images as Dimitri is putting into them labeling images; less, in fact, since it's less expensive for Dimitri to label images than it is for Bob to find and label them.
Again: image-label CAPTCHAs are doomed.
Your CAPTCHA is trivially cracked. Luckily for you, it's not worth a spammer's time to crack even that pathetic CAPTCHA, and so you don't get any spam. Now, try running a webmail service and see how long that lasts.
The point is that there are many solutions that work for smaller sites that simply do not stand up to concentrated attack. Webmail providers are especially vulnerable because throwaway email addresses enable many other kinds of malfeasance. Really, the problem we're talking about here isn't protecting your comment box. It's protecting large services against concentrated attack, and that's a much harder problem.
While that may be effective for the moment, as soon as a webmail provider starts using it, it'll be cracked overnight.
The problem is that CAs are subject to the "too big to fail" problem. Consider the Comodo certificate debacle -- Comodo delegated the authority to grant certificates to a third-party reseller, CertStar. CertStar then issued a certificate for mozilla.com with no validation whatsoever. This is about as big a breach of trust as a CA can manage short of publicly posting its master private key on a web page in China.
What happened? Fucking nothing happened. Sure, CertStar's wrist was slapped, and Comodo made a bunch of promises, but there were no reprisals, and no consequences. The Mozilla people refused to revoke the Comodo certificate because it would "break the web", and too many websites would stop working mysteriously.
What was the end result? Moral hazard for certificate authorities, and danger for users. My point is that CAs aren't fairies who are always magically correct. They're as vulnerable to incompetence and corruption as any institution.
(P.S.: I disable Comodo certificates in all browsers I use. I suggest you do the same thing.)
You fool -- what do you think our brains are except massively parallel computers? There's no conceptual barrier to better speech recognition. The problem is the same as image recognition, really, with one axis of a 2D image replaced with the time dimension of the recording. The arguments and counter-arguments that apply to image captchas also apply to audio ones just as well.
Audio catpcha crackers don't need to write dictation programs. Audio captchas as limited: you can't distort the signal too much: someone speaking in a thick Irish brogue will confuse many listeners. Words can't be particularly unfamiliar. The objects to be recognized must be familiar -- just as you can't expect random blog posters to type, say, Ancient Phoenician symbols into your captcha, you don't want to limit your posters to people with SAT verbal scores about 700 (however desirable a side-effect that might be).
While audio captchas might be effective for a little while, crackers will eventually figure out how to crack them, and we'll end up in the same place we are today. It's a classic Red Queen effect.
A CAPTCHA is not a Turing test. A Turing test requires that a person tell a computer and a human apart; the CAPTCHA problem is harder, from a certain point of view, because a computer is required to tell a human and a computer apart.
Everyone has a great idea for a CAPTCHA, but very few people know what the hell is really going on. Remember that the machine doesn't need to solve the CAPTCHA every time, that machines are infinitely patient and have huge memories, and that another machine needs to make sure the human gave the right answer!
Ideas that won't work:
Really, it's very easy to think you've come up with a very clever CAPTCHA. When you think that, all you've done is stoked your ego and screwed yourself over. It's the same reason why we don't roll our own cryptography: CAPTCHA-making is a very hard problem, mainly because your problem space must be infinite (to avoid an attacking machine simply memorizing answers), the answers verifiable by a machine, but the problems not solvable by a machine.
How many questions can be checked by machines but not answered by them?
Not many; fewer every day. There are no questions that can't be answered by a computer (and which can be answered by a human mind). The Church-Turing thesis [wikipedia.org] has some validity: the human mind is no more powerful than a turing machine, and ultimately, computers and our brains are equivalently computationally. There's nothing a computer can't solve: there are just things we haven't figured out yet.
Err, of course the USSR didn't count as first world. What I meant was "developed".
First-world nations had plenty of problems with their space programs at first too. Considering that North Korea has isolated itself, it's not surprising that they're going through the pain everyone else went through 60 years ago.
Sometimes it's hard to tell the difference between fanboyism and astroturfing.
The universe can do things you can't. Inflation is a change in the scale of the universe, not the motion of some object within it. They're entirely different effects.
That jet only appears to be superluminal due to the relative motion of the solar system and the jet's source. It's not actually moving faster than light in its own reference frame. Also, Hawking radiation doesn't count: we're dealing with distances on the order of a Planck length, where speed becomes meaningless. You might as well say particles do the Macarena as say that they move faster than light.
A bit solipsistic are we? There is an objective universe out there, and it obeys laws of causality and logic without our being involved at all. To imagine otherwise is arrogance (especially if your name is Penrose.)
That doesn't work. You can't transmit information faster than light; contrary to popular conception, quantum entanglement does not involve classical information transfer.
If you have one of a pair of dice, and the other is a thousand light-years away, one way to think of entanglement is to imagine that whatever number you roll is the number that shows up on the other die the next time it is rolled. Even if the two dice are linked, you can't control which number shows up, so you can't use the dice to communicate information.
Faster-than-light travel always causes causality paradoxes, so a priori, FTL drives are impossible unless special relativity is wrong. (That's is a bit like saying that perpetual motion machines are impossible unless thermodynamics is wrong.) The proposed mechanism behind the FTL drive doesn't matter -- it'll still cause a time paradox.
Just like we know any proposed perpetual motion machine must have a flaw, any proposed FTL drive must also have a flaw. They belong to the same class of impossible device, and deserve the same degree of consideration.
Nifty. Stark's been in office since 1973, but he only announced his atheism in 2007. Though he got 78% of the vote in 2008, he had a huge advantage in name recognition. For the next step, let's try to get a non-incumbent atheist elected.
I believe that this resolution is aimed at least in part at secular attacks on religion. As Gandhi said, "first they ignore you, then they laugh at you, then they fight you, then you win."
We atheists have been given the short shrift for a very long time now. First we were burned at the stake, then persecuted, and now we're gradually gaining mainstream acceptance now. We've gone from Bush the Elder claiming that atheists should be considered neither citizens nor patriots to Obama including non-believers in his inauguration speech. Perhaps in my lifetime, it'll be politically feasible for an atheist to hold an elected office.
It's no wonder that the religious old guard is running scared.
You did not understand my post. The sentence you mock comes from a section dealing with the common proposal for using the image classification problem as a CAPTCHA. More formally, in the classification approach, you have pre-existing images I_1, I_2, I_i and so on up to I_N. N is finite. Each image has a label L_1, L_2, L_i, ... L_N attached to it. The server sends the client a subset of the total set of images and asks for the corresponding labels (or equivalently, the server asks which images in the sent set have the given label attached.)
The trouble is that if N is small, it is possible to simply teach a malicious client about L_i for each i L. If such an algorithm exists, an attacker can use the same algorithm to generate the labels for the images the server sends as the challenge.
This discussion does not apply to the article's technique since the 3D captcha approach involved generated images; you're correct in that it's not amenable to a simple memorization attack. But as other posters have mentioned in this thread, 3D image recognition is essentially a solved problem algorithmically speaking, and it's only a matter of time before spammers learn to apply these algorithms in making their malicious clients.
If there's one pattern we see over and over again in CAPTCHA discussions, it's that an intuitive notion of what AI can do is flawed. You seem to think it's unlikely that a machine can recognize an arbitrarily-rotated 3D object, but they in fact can. Similar arguments apply to speech recognition, natural language parsing, route planning, and other tasks. Even if a particular problem doesn't yet have an algorithmic solution, it is only a matter before one is found: as the last part of my post indicated, the human mind is computationally equivalent to a Turing machine, and there is no problem that is fundamentally intractable for a computer that is not also fundamentally difficult for a human.
I must concede, however, that a Turing machine is merely an upper limit for the computational power of a human brain. As your post demonstrates, this limit gives some brains no trouble at all.
It's worse than that, actually. Remember, a machine doesn't need to pass the captcha every time. You only need to worry about re-training your image recognizer when the success rate falls below a useful level, and even very low levels of CAPTCHA success are useful for spammers.
Won't work. Where will you get your pictures of Siamese Cats? If you take them yourself, you'll only have a few. Spammers will simply train their bots to recognize these cats.
If you have lots of pictures of cat and non-cat objects, the attacker has two strategies: either he can get the same database you did (which you didn't make, because making a large enough database would be cost-prohibitive), or failing that, he just trains his image recognized to pick out characteristics of Siamese cats the same way a human brain would.
You know enough that recognizing 3D shapes is a solved problem; doesn't it seem clear that recognizing textures would be just as tractable?
And I imagine you could create tough cases, but these cases will also trip up human beings.
Oh, and there are problems computers can't (easily) solve, but can verify. The problem is that human brains can't solve these problems either!
Before someone jumps in with "humans can solve the halting problem!" -- we really can't. There are problems that obviously halt, and programs that obviously don't. We can tell these apart, but so can computers. It's the complicated, borderline cases that trip up both people and computers.
Furthermore, there are important caveats to the halting problem: first, you can tell whether a program halts in a given time. You just run it and see whether it halts! Human beings do this all the time when debugging hanging programs. We use a good heuristic that says "if a program doesn't quit after a good long while, it probably won't quit at all." (And that holds in most cases.)
Second, the halting problem can be solved, via brute force if necessary, for a restricted-memory machine. Make the available memory size small enough and you can actually perform useful validation. The proof of the halting problems' unsolvability applies only to unrestricted turing machines.
A true turing machine has never been built, and can't exist in our universe. Every computer is a limited-memory approximation.
Everyone has a great idea for a CAPTCHA, but very few people know what the hell is really going on. Remember that the machine doesn't need to solve the CAPTCHA every time, that machines are infinitely patient and have huge memories, and that another machine needs to make sure the human gave the right answer!
Ideas that won't work:
Really, it's very easy to think you've come up with a very clever CAPTCHA. When you think that, all you've done is stoked your ego and screwed yourself over. It's the same reason why we don't roll our own cryptography: CAPTCHA-making is a very hard problem, mainly because your problem space must be infinite (to avoid an attacking machine simply memorizing answers), the answers verifiable by a machine, but the problems not solvable by a machine.
How many questions can be checked by machines but not answered by them?
Not many; fewer every day. There are no questions that can't be answered by a computer (and which can be answered by a human mind). The Church-Turing thesis has some validity: the human mind is no more powerful than a turing machine, and ultimately, computers and our brains are equivalently computationally. There's nothing a computer can't solve: there are just things we haven't figured out yet.
Please don't use tinyurl unnecessarily. You could have directly linked to the pages you mention. It's impossible to tell where the links go when you use tinyurl.
David Swensen and Michael Schmidt proposed that newspapers simply receive endowments and operate off the interest, insulating them from commercial pressures and conflicts of interest. I think that's a fantastic idea, especially in conjunction with legal nonprofit status for newspapers.