That runs into the scalability problem that I mentioned--someone (say, a Mechanical Turk user) can solve that problem once, and put it in a database. To avoid this, there needs to be a way to generate them cheaply, so you pretty much need a computer that can solve the problem in the first place.
Basically, my point is that there's no such thing as "uniquely human intelligence". There's lots of problems that fall into that category now, but with the continuing rise of computational power, it's getting harder and harder to find new problems of this sort without excluding a lot of real people.
So that begins to look a bit like the RSA problem, doesn't it? Find a problem which can only be solved efficiently given some "secret" knowledge – where, instead of that knowledge (the prime factors) being secret, the knowledge is something it's easy for a computer to use but hard for it to recognize.
I'm probably overgeneralizing, but it's an interesting framing.
>To avoid this, there needs to be a way to generate them cheaply, so you pretty much need a computer that can solve the problem in the first place.
I don't see how that follows. Many captchas are just text with a confusing grid overlayed - that's incredibly trivial to produce, and producing one tells you next to nothing about how to solve them. Or if that's too easy, throw in some random distortion - still easy to produce, even harder to read.
Basically, my point is that there's no such thing as "uniquely human intelligence". There's lots of problems that fall into that category now, but with the continuing rise of computational power, it's getting harder and harder to find new problems of this sort without excluding a lot of real people.