Article
Version española (non-available yet)
Contents: 1) Absolute and relative super-recursive complexity; 2) Inductive Kolmogorov complexity
Super-recursive The Kolmogorov complexity C x) of an object (word) x with respect to an algorithm B from K is defined as
When x, we haveC x) £ C(_{T}x) + c_{UT}The machine x).Thus, the super-recursive the size of the shortest program (in number of symbols) for a universal in This measure is called There are many different classes of super-recursive algorithms:
the size of the shortest program (in number of symbols) for a universal inductive Turing machine of the first order This measure is called x | y). Namely, the IC(relative inductive Kolmogorov complexityx | y) of the word x relative to the word y is taken to be equal to:the size of the shortest program (in number of symbols) for a universal inductive Turing machine The inductive relative Kolmogorov complexity IC( x, i.e., information that can be extracted by inductive algorithms. Namely, we haveIC( The x with respect to an inductive Turing machine T is defined as
Burgin (1990; 1995) proved that there is an x). Namely, there is an inductive Turing machine U such that for any inductive Turing machine T, there is a constant c such that for all words _{T}x, we haveIC x) £ IC(_{T}x) + c_{T}The machine It is proved (Burgin, 2005) that inductive Kolmogorov complexity for a word At the same time, many properties of inductive Kolmogorov complexity are similar to the properties of the conventional Kolmogorov complexity For instance, when the length of a word tends to infinity, its inductive Kolmogorov complexity also tends to infinity. 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.
| 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 entriesWhenever an entry is integrated in the article (left column) the corresponding entry is reflected in this section. Burgin (17/02/2011)[After review, the article was moved to the article column on 16/12/2011] |

Glossary (en) >