computation

Is there any difference in kind, rather than of degree, between Amazon’s Mechanical Turk, the now-defunct Google Answers, and Wikipedia? I contend that they are all doing the same thing – using people as computational objects in a larger system. The people are solving tasks that computers aren’t good at, but they are essentially acting as function calls. In Mechanical Turk, the tasks are well-defined and very small. In Google answers, the tasks are fuzzier, but still explicit. In Wikipedia, the tasks are threefold: identify inaccuracies, clean up, and fill in missing pieces.

Viewing these systems from a computational point of view is all of a sudden kind of interesting. We are using people as function calls – can we talk about “Human-Hard” problems? How about “Non-deterministic human-hard problems”? In this video from MIT’s technology review, evolutionary design is discussed. And this design process is exactly for a computer to generate a lot of candidate solutions, followed by a human marking the solutions on a scale from good to bad. The computer then uses the better solutions to generate more solutions, which the user then scores again. In this way, the computer/human combo hopes to zero in on good solutions to the problem.

Pornography is the classic non-deterministic human-hard problem. People can identify pornography when they see it, (i.e. verify the solution), but they cannot come up with an efficient description of what they are looking for.

* you clicked that link, didn’t you?

Using people as computational objects all of a sudden puts these systems squarely in the domain of people who look at algorithms and the complexity of systems. Using these tools, hopefully we could generalize to figure out what problems would be difficult for a human/machine combo, and what problems could be easy.

We could even move forward from this more limited view, and try and develop a general theory of computational object combination. Turing machines are good at some things, quantum computers are good at others, and people are good at yet more stuff. When we combine these systems, in different ways, how much more can we accomplish? What can we accomplish with only $O(n)$ calls to the “human please identify this” function? What about $O(1)$ or $O(\lg n)$? What if we have quantum computers and human computers and Turing machines? Do we now have more power?

This is a lot like computational complexity and computing with oracles, and it also to relates to some work that is just in the beginning stages where people are trying to articulate what it means for a program to be hard for a genetic algorithm to solve. Because clearly, some things are efficiently solvable by genetic algorithms, and some things are not. Well, the same applies to humans, and to everything else that can try and solve a problem. What problems are self-assembling-nanotech-hard? What problems are DNA-based evolution-hard? Once you start looking at the universe as a computational object your brain kind of goes a bit nuts, but I’m pretty sure that not all of these ideas are crap… This seems to relate to the tossed off comment of Neal Gershenfeld (at minute 4:49) about the narrow focus of computer science: