Lecture: Human Computation
Manuel Blum
Abstract:
A source of power for theoretical computer science has been the interplay of algorithms and complexity: given a computational problem to be solved, algorithm design is concerned with finding faster solutions than what is currently available. Complexity theory is concerned with showing that faster solutions are impossible.
When a faster algorithm appears impossible to get, one can sometimes use that intuition to raise the complexity lower bound.
When the complexity lower bound appears impossible to raise, one can sometimes use that intuition to construct a faster algorithm.
This is the well-known point and counterpoint of modern theoretical computer science.
The goal of human computability is to do the same thing - to build the same kind of theory - to get the same kind of algorithmic upper bounds and complexity theoretic lower bounds for the kinds of computations that humans can do in their heads.
