Contents: 1) Absolute and relative complexity measures; 2) Complexity with respect to an algorithm; 3) Absolute Kolmogorov complexity; 4) Diversity of naming, approaches and applications.
Kolmogorov complexity is an algorithmic measure or measure of algorithmic information. It is defined for constructive objects, such as words in some alphabet. If the size of the shortest program (in number of symbols) for a universal Turing machine As Turing machines are recursive algorithms, the original Kolmogorov complexity C( This measure is called
The relative Kolmogorov complexity C( I(
The Kolmogorov complexity C x) of an object (word) x with respect to an algorithm A is defined as
If the
Solomonoff (1964), Kolmogorov (1965), and Chaitin (1969) proved that there is an invariant up to some additive constant Kolmogorov complexity C( x, we haveC x) £ C(_{T}x) + c_{UT}The machine x).However, it is necessary to understand that this invariance is not absolute because the value of the constant U (Weinstein, 2003; Burgin, 2005).It was demonstrated that Kolmogorov complexity cannot be computed by a Turing machine or by any other recursive algorithm (Kolmogorov, 1965) but can be computed by an inductive Turing machine (Burgin, 1982). When the length of a word tends to infinity, its Kolmogorov complexity also tends to infinity.
Although the majority of researchers use Different names reflect different approaches to the concept. When we want to know how difficult it might be computing or constructing some object Kolmogorov, or algorithmic, complexity has become an important and popular Many Existence of different versions of Kolmogorov complexity caused a necessity to build a unified algorithmic information measure. Such a theory has been developed as an References
- BURGIN, M. (1982) Generalized Kolmogorov complexity and duality in theory of computations, Soviet Math. Dokl., v.25, No. 3, pp. 19–23
- BURGIN, M. (1990) Generalized Kolmogorov Complexity and other Dual Complexity Measures, Cybernetics, No. 4, pp. 21–29
- BURGIN, M. (1995) Algorithmic Approach in the Dynamic Theory of Information,
*Notices of the Russian Academy of Sciences*, v. 342, No. 1, pp. 7-10 - BURGIN, M. (2005)
*Super-recursive algorithms*, Monographs in computer science, Springer. - BURGIN, M. (2010)
*Theory of Information: Fundamentality, Diversity and Unification*. Singapore: World Scientific Publishing - BURGIN, M.
*International Journal of Computing & Information Technology*, 2010, v. 2, No. 1, pp. 149-187 - CHAITIN, G. J. (1969). "On the Simplicity and Speed of Programs for Computing Infinite Sets of Natural Numbers" (PDF).
*Journal of the ACM***16**: 407. - CHAITIN, G.J. (1976) Information theoretic characterizations of recursive infinite strings.
*Theoretical Computer Science*, v. 2, pp. 45–48 - CHAITIN, G.J. (1977) Algorithmic information theory,
*IBM Journal of Research and Development*, v.21, No. 4, pp. 350-359 - KOLMOGOROV, A.N. (1965). "Three Approaches to the Quantitative Definition of Information".
*Problems Inform. Transmission***1**(1): 1–7. - SCHMIDHUBER, J. (2002) Hierarchies of Generalized Kolmogorov Complexities and Nonenumerable Universal Measures Computable in the Limit,
*International Journal of**Foundations of Computer Science*, v. 3, No. 4, pp. 587-612 - SOLOMONOFF, R. (June 1964). "A Formal Theory of Inductive Inference Part II".
*Information and Control***7**(2): 224–254. - SOLOMONOFF, R. (March 1964). "A Formal Theory of Inductive Inference Part I".
*Information and Control***7**(1): 1–22. - SVOZIL. K. (1996) Quantum Algorithmic Information Theory,
*Journal of Universal Computer Science*, v. 2, pp. 311-346 - WEINSTEIN, S.
*Objectivity, information, and Maxwell's demon*, Preprint, PhilSci-Archive, 2003. [Online] <http://philsci-archive.pitt.edu/> (accessed: 14/3/2015)
| Entries
New entry. For doing a new entry: (1) the user must be identified as an authorized user(to this end, the "sign in" link at the page bottom left can be followed). (2) After being identified, press the "edit page" button at he upper right corner. (3) Being in edition mode, substitute -under this blue paragraph- "name" by the authors' names, "date" by the date in which the text is entered; and the following line by the proposed text. At the bottom of the entry, the references -used in the proposed text- must be given using the normalized format. (4) To finish, press the "save" button at the upper right corner.The entry will be
reviewed by the editor and -at least- another peer, and subsequently articulated in the article if elected.Name (dd/mm/yyyy)[To be substituted by the author with the proposed text] Incorporated entries
Whenever an entry is integrated in the article (left column) the corresponding entry is reflected in this section.
Mark Burgin (17/2/2011)[The entry was moved to the article column after review on 16/12/2011] |

Glossary (en) >