Complex Systems

Complexity, Depth, and Sophistication Download PDF

Moshe Koppel
Queens College, Flushing, NY 11367, USA

Abstract

Two measures of the "meaingful" complexity of an infinite string are shown to be equivalent up to a constant (under appropriate translation). "Sophistication," defined by Koppel and Atlan [3], is the size of the projectible part of the string's minimal description and formalizes the amount of planning which went into the construction of the string. "Depth," defined by Bennett [1], is the amount of time required for the string to be generated from its minimal description and formalizes its "evolvedness."