lotus



previous page: 22 Information Theory References - Adleman and papers related tomolecular computation
  
page up: Biological Information Theory and Chowder Society FAQ
  
next page: 24 Information Theory References - Chris Hillman and papers related to entropy

23 Information Theory References - Gad Yagil and papers related toalgorithmic information theory




Description

This article is from the Biological Information Theory and Chowder Society FAQ, by Thomas D. Schneider toms@ncifcrf.gov.

23 Information Theory References - Gad Yagil and papers related toalgorithmic information theory

(AIT) or Algorithmic Complexity

An alternative way to analyze biosystems is by the Algorithmic Information
Theory (AIT) or Algorithmic Complexity (AC) approach, first formulated by
Kolmogoroff, Solomonoff and Chaitin in the 1960's. According to this
approach, the information in a string of symbols is equal to the length of
the shortest program caparisons of reproducing the string. This concept has
been reformulated to tackle real molecular and biosystems ("Structural
Complexity") and applied to a range of biosystems by G. Yagil. The more
recent publications, which include references to the work of Kolmogoroff and
of Chaitin, can be found at:

http://www.weizmann.ac.il/~lcyagil
also at http://interjournal.org, Manuscript Number 135. (Do a search for the
manuscript number.)

The book of Cover and Thomas covers AC extensively. In particular, it shows
that under certain conditions, AC can become equal to the Shannon
information (or uncertainty) measure. In a series of papers, C.H. Bennett
has proposed a concept of "logical depth", related to the time required by a
universal machine to compute a sequence, as another measure of the
information content of a string or sequence:

see: C.H. Bennett, "Logical Depth and Physical Complexity". In: "The
Universal Turing Machine -A half century", Rolf Herken, Editor, Oxford
University press, 1988.

Gad Yagil, Ph. D.
Dept. of Molecular Cell Biology
The Weizmann Institute of Science
Rehovot, Israel, 76100
Tel. 089-460-918 (home)
Fax 089-344-125
e-mail lcyagil@wiccmail.weizmann.ac.il.

 

Continue to:













TOP
previous page: 22 Information Theory References - Adleman and papers related tomolecular computation
  
page up: Biological Information Theory and Chowder Society FAQ
  
next page: 24 Information Theory References - Chris Hillman and papers related to entropy