If only we could invent the verbal equivalent of a trapdoor function. A word puzzle that would be extremely easy for computers to generate and humans to solve (since we understand language), but extremely hard for computers to solve.
It's a nice idea, but you have to consider the complexity of the word puzzles compared to the average human's brain power. Most people are quite dumb. If there aren't a sufficient number of problems/answers, or they're simple enough for computers to solve, or they're too complex for a minority of humans to solve, you're boned.
The whole thing is a technology arm's race. The best solution would be one where you simply verify fixed private information. We use captchas for verifying a human being is not a bot, right? And we do that because we assume the user is anonymous for a short time.
Instead we could simply provide a secured authentication gateway where one could provide private information that is linked to a human identity. That way it can't be abused unless they have an unlimited supply of stolen identities. Even better would be if everyone signed up for a TOTP service provider and used their token generator and service-account to prove their human-ness without needing to put in sensitive information. But that's probably too much work.
I know what you're trying to say here, but consider today's xkcd[0] as a counter-point. I think "most people" are quite capable of solving a lot of puzzles. This issue is that any puzzle that we can solve in a reasonable timeframe is often a good target for a computer-generated solution as well.
The xkcd is only necessarily true when it is the median average that is considered. However, most people are not necessarily of mean average intelligence.
Except you lose the benefit of anonymity, which is a big draw for many of the places using Captchas. Unless I don't understand your idea, which is possible.
Well anonymity isn't the purpose of captchas. Captchas are intended to provide human-confirmation with the least friction possible, mainly for rate-limiting of services. Having to establish you are a specific individual takes effort, but just typing in a random word is simple. Anonymity is just a by-product of the frictionless [simple] part.
You can still come up with new ways to verify someone is a human for specific uses where you want anonymity, but they will always be part of the tech arms race if you want them frictionless. To avoid them getting more annoying you need a way to authenticate an individual identity, as that allows you to rate-limit access.
You could, of course, do TOTP and totally preserve anonymity. Unless the TOTP service provider is compromised, in which case all bets are off (but perfect-forward secrecy might solve that?)
Anonymity is not just a byproduct of frictionless experience. It used to be a fundamental part of most interaction on the web (on the internet no one knows you're a dog, etc.).
I agree that anonymity is orthogonal to the purpose of captchas, but usually a captcha is only required when you don't have identity. This can be because you haven't established identity, or because the identity is in question, but also because the site does not want to require identity. In fact, outside of first time user sign ups, most captchas are used specifically to allow people to engage without needing an account. So in most cases you use a captcha because you want to allow anonymity.
There already exists several systems like you describe: login with your Google account, Facebook, Twitter. There are already several comment systems (Disqus for example) which make using these as simple as using a captcha for sites who don't care about anonymity. We don't need to integrate identity into captchas.
