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.

Imagine a friend asks: "could you pass me the dragonfruit''. You have no idea what they mean and inquire, "do you mean the orange fruit in the bowl?'', but they respond: "no, the pink one''. Now you know which fruit they want and in future contexts you will likely also understand their request. People seamlessly update beliefs about speakers' (word) meanings. Through interaction they somehow infer what "dragonfruit'' means: are all dragonfruits "pink'', or just this one? Is its shape more diagnostic, or some combination of the two? The number of possible belief updates is vast, growing exponentially with the number of features. Using formal complexity analysis, we prove that state-of-the-art models of communication are computationally intractable. Hence, they cannot yet explain how people can navigate this search space efficiently and communicate seamlessly. The intractability result holds for different model variants, suggesting a fundamental computational challenge for explaining communicative interaction.

Computational model simulations have been very fruitful for gaining insight into how the systematic structure we observe in the world's natural languages could have emerged through cultural evolution. However, these model simulations operate on a toy scale compared to the size of actual human vocabularies, due to the prohibitive computational resource demands that simulations with larger lexicons would pose. Using computational complexity analysis, we show that this is not an implementational artifact, but instead it reflects a deeper theoretical issue: these models are (in their current formulation) computationally intractable. This has important theoretical implications, because it means that there is no way of knowing whether or not the properties and regularities observed for the toy models would scale up. All is not lost however, because awareness of intractability allows us to face the issue of scaling head-on, and can guide the development of our theories.