Proceedings of the Annual Meeting of the Cognitive Science Society

Many researchers in AI and Cognitive Science believe that the information processing complexity of a mecha- nism is reflected in the complexity of a description of its behavior. In this paper, w e distinguish two types of com- plexity and demonstrate that neither one can be an objective property of the underlying physical system. A shift in the method or granularity of observation can cause a system's behavioral description to change in both the number of apparent states and the complexity class. These examples demonstrate h o w the act of obser- vation itself can suggest frivolous explanations of physi- cal phenomena, up to and including computation.