How hard is cognitive science?

Cognitive science is itself a cognitive activity. Yet, computational cognitive science tools are seldom used to study (limits of) cognitive scientists' thinking. Here, we do so using computational-level modeling and complexity analysis. We present an idealized formal model of a core inference problem faced by cognitive scientists: Given observations of a system's behaviors, infer cognitive processes that could plausibly produce the behavior. We consider variants of this problem at different levels of explanation and prove that at each level, the inference problem is intractable, or even uncomputable. We discuss the implications for cognitive science.