Measuring complexity of intelligent machines

A formalism that combines reliability and complexity as performance measures for intelligent machines is introduced. For a given desired reliability, different algorithms may be available which are reliable enough. Hence, it is important to have a means of choosing the algorithm of least cost among the reliable ones. Cost refers not only to CPU time, but also to other features, such as memory space. Information-based complexity provides a solid formalism for dealing with different sources of information and thus distinct algorithms at all levels of the machine. A case study related to image processing illustrates the method