Paper Info
Title
The Evolution and Understanding of Hierarchical Complexity in Biology from an Algebraic Perspective
Abstract
We develop the rigorous notion of a model for understanding state transition systems by hierarchical coordinate systems. Using this we motivate an algebraic definition of the complexity of biological systems, comparing it to other candidates such as genome size and number of cell types. We show that our complexity measure is the unique maximal complexity measure satisfying a natural set of axioms. This reveals a strong relationship between hierarchical complexity in biological systems and the area of algebra known as global semigroup theory. We then study the rate at which hierarchical complexity can evolve in biological systems assuming evolution is “as slow as possible” from the perspective of computational power of organisms. Explicit bounds on the evolution of complexity are derived showing that, although the evolutionary changes in hierarchical complexity are bounded, in some circumstances complexity may more than double in certain “genius jumps” of evolution. In fact, examples show that our bounds are sharp. We sketch the structure where such complexity jumps are known to occur and note some similarities to previously identified mechanisms in biological evolutionary transitions. We also address the question of, How fast can complexity evolve over longer periods of time? Although complexity may more than double in a single generation, we prove that in a smooth sequence of t “inclusion” steps, complexity may grow at most from N to .N C 1/t C N, a linear function of number of generations t, while for sequences of “mapping” steps it increases by at most t. Thus, despite the fact that there are major transitions in which complexity jumps are possible, over longer periods of time, the growth of complexity may be broken into maximal intervals on which it is bounded above in the- manner described.
Year
DOI
Venue
2000
10.1162/106454600568311
Artificial Life
Keywords
Field
DocType
krohn-rhodes theory,algebra,algebraic automata theory,biological computation,bounds on rates of evolution,coordinate systems for understanding,evolution of complexity,measures of complexity,semigroups,biological systems,automata theory,coordinate system,genome size,satisfiability,computer algebra
PH,Quantum complexity theory,Asymptotic computational complexity,Structural complexity theory,Model of hierarchical complexity,Computer science,Complexity index,Descriptive complexity theory,Artificial intelligence,Machine learning,Game complexity
Journal
Volume
Issue
ISSN
6
1
1064-5462
Citations 
PageRank 
References 
20
2.43
5
Authors
2
Name
Order
Citations
PageRank
Chrystopher L. Nehaniv11219138.00
John L. Rhodes2203.11