Formalization, Complexity, and Adaptive Rationality
Dissertation, University of Minnesota (
1994)
Copy
BIBTEX
Abstract
This work examines the importance of distinguishing different levels of psychological explanation and the primacy of the computational level over implementational levels. The framework of levels allows us to recognize the role of formal theories as tools for specifying reasoning tasks at the computational level. It is shown that formal specifications of reasoning tasks allow us to analyze the complexity of the specified tasks and also serve to define reasoning competence and performance errors. Complexity analysis helps us identify tractable, practically significant, subclasses of inference. The identification of these subclasses provides useful ante hoc and post hoc specifications for AI programming projects and psychological modeling. Formalization and complexity analysis also enable us to examine tradeoffs between tractability and range of applicability of implementations of a reasoning task. It is undesirable to obtain tractability at the expense of limiting the applicability of a cognitive mechanism to an unreal situation or a toy domain. It is argued that this undesirable result can be avoided if we examine the structure of the environment in which a mechanism is supposed to work and the environmental assumptions that make the computation tractable. Finally, it is demonstrated that many problems the human mind needs to solve in normal environments are indeed tractable and that the mind is equipped with adaptive mechanisms to solve them efficiently. This demonstration undermines a skeptical challenge to human rationality based on claims that many problems are intractable and that the capacity of the human mind is limited