Complexity, D epth, and Sophistication
Moshe Koppel · 1987
T wo measures of t he meaning ful com plex ity of a n infi ni te string ar e sho wn to be equivalent up to a const a nt ( under appro priate tran slati on) . So phis t ica tion, defined by Ko ppel a nd Atlan (3), is t he siz e of t he pr oj ectible par t of t he s t r ing's minima l d escription and forma lizes t he amount of pla nni ng which wen t into t he constru c t ion of the string. Dept h. defi ned by Bennett til, is t he a mou nt o f t ime require d for t he string to be generated from its min ima l des cr ip tio n and formal izes its evolved ness.