# 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: