If you're curious about how the algorithm works, here's a recent talk from one of the authors of the paper where he talks about it: http://www.youtube.com/watch?v=iK3HIIsZGJY&t=1m32s

As to your questions, I think the way it's going with these convolutional neural nets, the idea of being able to tell a human from a computer with something like captcha isn't going to work. I'm thinking a captcha that still would work would be a randomly generated natural language instruction that a user has to interpret with some top down reasoning (possibly with a natural text answer). We've still got a ways to go before we can do that really effectively with software.