Complexity, Depth, and Sophistication
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."
