50 years ago this summer, McCarthy, Minsky, Rochester, and Shannon organized a summer conference at Dartmouth which turned out to be a milestone in Artificial Intelligence research. For the logically minded, this item in the funding proposal to the Rockefeller Foundation is perhaps most interesting:
4. Theory of the Size of a Calculation
If we are given a well-defined problem (one for which it is possible to test mechanically whether or not a proposed answer is a valid answer) one way of solving it is to try all possible answers in order. This method is inefficient, and to exclude it one must have some criterion for efficiency of calculation. Some consideration will show that to get a measure of the efficiency of a calculation it is necessary to have on hand a method of measuring the complexity of calculating devices which in turn can be done if one has a theory of the complexity of functions. Some partial results on this problem have been obtained by Shannon, and also by McCarthy.