The observers' paradox: apparent computational complexity in physical systems

Abstract

Many researchers in AI and cognitive science believe that the complexity of a behavioural description reflects the underlying information processing complexity of the mechanism producing the behaviour. This paper explores the foundations of this complexity assumption. We first distinguish two types of complexity judgements that can be applied to these descriptions and then argue that neither type can be an intrinsic property of the underlying physical system. In short, we demonstrate how changes in the method of observation can radically alter both the number of apparent states and the apparent generative class of a system's behavioural description. From these examples we conclude that the act of observation can suggest frivolous computational explanations of physical phenomena, up to and including cognition.