Document (#43603)

Author

Chaitin, G.J.

Title

Algorithmic information theory

Source

IBM journal research and development. 21(1977) no.4, S.350-359

Year

1977

Abstract

This paper reviews algorithmic information theory, which is an attempt to apply information-theoretic and probabilistic ideas to recursive function theory. Typical concerns in this approach are, for example, the number of bits of information required to specify an algorithm, or the probability that a program whose bits are chosen by coin flipping produces a given output. During the past few years the definitions of algorithmic information theory have been reformulated. The basic features of the new formalism are presented here and certain results of R. M. Solovay are reported.

Content

DOI: 10.1147/rd.214.0350.

Footnote

Vgl.: https://ieeexplore.ieee.org/document/5390997.

Theme

Information

Similar documents (author)

1. Chaitin, G.J.: Gödel's theorem and information (1982) 6.01

   6.0137663 = sum of:
     6.0137663 = weight(author_txt:chaitin in 2447) [ClassicSimilarity], result of:
       6.0137663 = fieldWeight in 2447, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         9.622026 = idf(docFreq=7, maxDocs=44421)
         0.625 = fieldNorm(doc=2447)
   

2. Chaitin, G.: ¬Die Grenzen der Gewissheit (2006) 6.01

   6.0137663 = sum of:
     6.0137663 = weight(author_txt:chaitin in 4478) [ClassicSimilarity], result of:
       6.0137663 = fieldWeight in 4478, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         9.622026 = idf(docFreq=7, maxDocs=44421)
         0.625 = fieldNorm(doc=4478)
   

3. Chaitin, G.J.: ¬The limits of mathematics (1997) 6.01

   6.0137663 = sum of:
     6.0137663 = weight(author_txt:chaitin in 974) [ClassicSimilarity], result of:
       6.0137663 = fieldWeight in 974, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         9.622026 = idf(docFreq=7, maxDocs=44421)
         0.625 = fieldNorm(doc=974)
   

4. Chaitin, G.J.: Conversations with a mathematician : Math, art, science and the limits of reason (2002) 6.01

   6.0137663 = sum of:
     6.0137663 = weight(author_txt:chaitin in 3212) [ClassicSimilarity], result of:
       6.0137663 = fieldWeight in 3212, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         9.622026 = idf(docFreq=7, maxDocs=44421)
         0.625 = fieldNorm(doc=3212)
   

5. Chaitin, G.J.: Grenzen der Berechenbarkeit (2004) 6.01

   6.0137663 = sum of:
     6.0137663 = weight(author_txt:chaitin in 3422) [ClassicSimilarity], result of:
       6.0137663 = fieldWeight in 3422, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         9.622026 = idf(docFreq=7, maxDocs=44421)
         0.625 = fieldNorm(doc=3422)
   

Similar documents (content)

1. Chaitin, G.J.: Algorithmic information theory (1987) 0.42

   0.41775906 = sum of:
     0.41775906 = product of:
       1.305497 = sum of:
         0.05967775 = weight(abstract_txt:program in 175) [ClassicSimilarity], result of:
           0.05967775 = score(doc=175,freq=1.0), product of:
             0.09584722 = queryWeight, product of:
               1.0155221 = boost
               5.6926546 = idf(docFreq=406, maxDocs=44421)
               0.016579647 = queryNorm
             0.6226341 = fieldWeight in 175, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.6926546 = idf(docFreq=406, maxDocs=44421)
               0.109375 = fieldNorm(doc=175)
         0.087848075 = weight(abstract_txt:chosen in 175) [ClassicSimilarity], result of:
           0.087848075 = score(doc=175,freq=1.0), product of:
             0.1240298 = queryWeight, product of:
               1.1552145 = boost
               6.475721 = idf(docFreq=185, maxDocs=44421)
               0.016579647 = queryNorm
             0.708282 = fieldWeight in 175, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.475721 = idf(docFreq=185, maxDocs=44421)
               0.109375 = fieldNorm(doc=175)
         0.14906399 = weight(abstract_txt:probability in 175) [ClassicSimilarity], result of:
           0.14906399 = score(doc=175,freq=2.0), product of:
             0.14004783 = queryWeight, product of:
               1.2275462 = boost
               6.881186 = idf(docFreq=123, maxDocs=44421)
               0.016579647 = queryNorm
             1.0643791 = fieldWeight in 175, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               6.881186 = idf(docFreq=123, maxDocs=44421)
               0.109375 = fieldNorm(doc=175)
         0.15918133 = weight(abstract_txt:theoretic in 175) [ClassicSimilarity], result of:
           0.15918133 = score(doc=175,freq=1.0), product of:
             0.18434554 = queryWeight, product of:
               1.4083674 = boost
               7.894805 = idf(docFreq=44, maxDocs=44421)
               0.016579647 = queryNorm
             0.8634943 = fieldWeight in 175, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.894805 = idf(docFreq=44, maxDocs=44421)
               0.109375 = fieldNorm(doc=175)
         0.28818244 = weight(abstract_txt:coin in 175) [ClassicSimilarity], result of:
           0.28818244 = score(doc=175,freq=1.0), product of:
             0.27383116 = queryWeight, product of:
               1.7164892 = boost
               9.622026 = idf(docFreq=7, maxDocs=44421)
               0.016579647 = queryNorm
             1.0524092 = fieldWeight in 175, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               9.622026 = idf(docFreq=7, maxDocs=44421)
               0.109375 = fieldNorm(doc=175)
         0.032374747 = weight(abstract_txt:information in 175) [ClassicSimilarity], result of:
           0.032374747 = score(doc=175,freq=2.0), product of:
             0.086527765 = queryWeight, product of:
               2.1575575 = boost
               2.4188995 = idf(docFreq=10748, maxDocs=44421)
               0.016579647 = queryNorm
             0.37415442 = fieldWeight in 175, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               2.4188995 = idf(docFreq=10748, maxDocs=44421)
               0.109375 = fieldNorm(doc=175)
         0.12027299 = weight(abstract_txt:theory in 175) [ClassicSimilarity], result of:
           0.12027299 = score(doc=175,freq=1.0), product of:
             0.242756 = queryWeight, product of:
               3.232322 = boost
               4.529811 = idf(docFreq=1301, maxDocs=44421)
               0.016579647 = queryNorm
             0.49544805 = fieldWeight in 175, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.529811 = idf(docFreq=1301, maxDocs=44421)
               0.109375 = fieldNorm(doc=175)
         0.40889573 = weight(abstract_txt:algorithmic in 175) [ClassicSimilarity], result of:
           0.40889573 = score(doc=175,freq=1.0), product of:
             0.4986778 = queryWeight, product of:
               4.0120864 = boost
               7.496775 = idf(docFreq=66, maxDocs=44421)
               0.016579647 = queryNorm
             0.81995976 = fieldWeight in 175, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.496775 = idf(docFreq=66, maxDocs=44421)
               0.109375 = fieldNorm(doc=175)
       0.32 = coord(8/25)
   

2. Klir, G.I.; Wierman, M.J.: Uncertainty-based information : Elements of generalized information theory (1998) 0.08

   0.083057 = sum of:
     0.083057 = product of:
       0.51910627 = sum of:
         0.06512327 = weight(abstract_txt:ideas in 969) [ClassicSimilarity], result of:
           0.06512327 = score(doc=969,freq=1.0), product of:
             0.092939585 = queryWeight, product of:
               5.6056433 = idf(docFreq=443, maxDocs=44421)
               0.016579647 = queryNorm
             0.7007054 = fieldWeight in 969, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.6056433 = idf(docFreq=443, maxDocs=44421)
               0.125 = fieldNorm(doc=969)
         0.120461896 = weight(abstract_txt:probability in 969) [ClassicSimilarity], result of:
           0.120461896 = score(doc=969,freq=1.0), product of:
             0.14004783 = queryWeight, product of:
               1.2275462 = boost
               6.881186 = idf(docFreq=123, maxDocs=44421)
               0.016579647 = queryNorm
             0.86014825 = fieldWeight in 969, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.881186 = idf(docFreq=123, maxDocs=44421)
               0.125 = fieldNorm(doc=969)
         0.026162745 = weight(abstract_txt:information in 969) [ClassicSimilarity], result of:
           0.026162745 = score(doc=969,freq=1.0), product of:
             0.086527765 = queryWeight, product of:
               2.1575575 = boost
               2.4188995 = idf(docFreq=10748, maxDocs=44421)
               0.016579647 = queryNorm
             0.30236244 = fieldWeight in 969, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               2.4188995 = idf(docFreq=10748, maxDocs=44421)
               0.125 = fieldNorm(doc=969)
         0.30735838 = weight(abstract_txt:theory in 969) [ClassicSimilarity], result of:
           0.30735838 = score(doc=969,freq=5.0), product of:
             0.242756 = queryWeight, product of:
               3.232322 = boost
               4.529811 = idf(docFreq=1301, maxDocs=44421)
               0.016579647 = queryNorm
             1.2661207 = fieldWeight in 969, product of:
               2.236068 = tf(freq=5.0), with freq of:
                 5.0 = termFreq=5.0
               4.529811 = idf(docFreq=1301, maxDocs=44421)
               0.125 = fieldNorm(doc=969)
       0.16 = coord(4/25)
   

3. Wong, S.K.M.: On modelling information retrieval with probabilistic inference (1995) 0.08

   0.07668306 = sum of:
     0.07668306 = product of:
       0.38341528 = sum of:
         0.04884245 = weight(abstract_txt:ideas in 2006) [ClassicSimilarity], result of:
           0.04884245 = score(doc=2006,freq=1.0), product of:
             0.092939585 = queryWeight, product of:
               5.6056433 = idf(docFreq=443, maxDocs=44421)
               0.016579647 = queryNorm
             0.525529 = fieldWeight in 2006, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.6056433 = idf(docFreq=443, maxDocs=44421)
               0.09375 = fieldNorm(doc=2006)
         0.12151319 = weight(abstract_txt:probabilistic in 2006) [ClassicSimilarity], result of:
           0.12151319 = score(doc=2006,freq=2.0), product of:
             0.13543826 = queryWeight, product of:
               1.2071753 = boost
               6.7669935 = idf(docFreq=138, maxDocs=44421)
               0.016579647 = queryNorm
             0.8971851 = fieldWeight in 2006, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               6.7669935 = idf(docFreq=138, maxDocs=44421)
               0.09375 = fieldNorm(doc=2006)
         0.090346426 = weight(abstract_txt:probability in 2006) [ClassicSimilarity], result of:
           0.090346426 = score(doc=2006,freq=1.0), product of:
             0.14004783 = queryWeight, product of:
               1.2275462 = boost
               6.881186 = idf(docFreq=123, maxDocs=44421)
               0.016579647 = queryNorm
             0.6451112 = fieldWeight in 2006, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.881186 = idf(docFreq=123, maxDocs=44421)
               0.09375 = fieldNorm(doc=2006)
         0.01962206 = weight(abstract_txt:information in 2006) [ClassicSimilarity], result of:
           0.01962206 = score(doc=2006,freq=1.0), product of:
             0.086527765 = queryWeight, product of:
               2.1575575 = boost
               2.4188995 = idf(docFreq=10748, maxDocs=44421)
               0.016579647 = queryNorm
             0.22677183 = fieldWeight in 2006, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               2.4188995 = idf(docFreq=10748, maxDocs=44421)
               0.09375 = fieldNorm(doc=2006)
         0.103091136 = weight(abstract_txt:theory in 2006) [ClassicSimilarity], result of:
           0.103091136 = score(doc=2006,freq=1.0), product of:
             0.242756 = queryWeight, product of:
               3.232322 = boost
               4.529811 = idf(docFreq=1301, maxDocs=44421)
               0.016579647 = queryNorm
             0.42466977 = fieldWeight in 2006, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.529811 = idf(docFreq=1301, maxDocs=44421)
               0.09375 = fieldNorm(doc=2006)
       0.2 = coord(5/25)
   

4. Pross, T.: ¬An action-theory-based treatment of temporal individuals (2014) 0.08

   0.07569092 = sum of:
     0.07569092 = product of:
       0.37845457 = sum of:
         0.0793214 = weight(abstract_txt:specify in 4408) [ClassicSimilarity], result of:
           0.0793214 = score(doc=4408,freq=1.0), product of:
             0.1682636 = queryWeight, product of:
               1.3455341 = boost
               7.5425844 = idf(docFreq=63, maxDocs=44421)
               0.016579647 = queryNorm
             0.47141153 = fieldWeight in 4408, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.5425844 = idf(docFreq=63, maxDocs=44421)
               0.0625 = fieldNorm(doc=4408)
         0.090960756 = weight(abstract_txt:theoretic in 4408) [ClassicSimilarity], result of:
           0.090960756 = score(doc=4408,freq=1.0), product of:
             0.18434554 = queryWeight, product of:
               1.4083674 = boost
               7.894805 = idf(docFreq=44, maxDocs=44421)
               0.016579647 = queryNorm
             0.4934253 = fieldWeight in 4408, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.894805 = idf(docFreq=44, maxDocs=44421)
               0.0625 = fieldNorm(doc=4408)
         0.097895764 = weight(abstract_txt:formalism in 4408) [ClassicSimilarity], result of:
           0.097895764 = score(doc=4408,freq=1.0), product of:
             0.19360022 = queryWeight, product of:
               1.4432865 = boost
               8.090549 = idf(docFreq=36, maxDocs=44421)
               0.016579647 = queryNorm
             0.50565934 = fieldWeight in 4408, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               8.090549 = idf(docFreq=36, maxDocs=44421)
               0.0625 = fieldNorm(doc=4408)
         0.013081373 = weight(abstract_txt:information in 4408) [ClassicSimilarity], result of:
           0.013081373 = score(doc=4408,freq=1.0), product of:
             0.086527765 = queryWeight, product of:
               2.1575575 = boost
               2.4188995 = idf(docFreq=10748, maxDocs=44421)
               0.016579647 = queryNorm
             0.15118122 = fieldWeight in 4408, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               2.4188995 = idf(docFreq=10748, maxDocs=44421)
               0.0625 = fieldNorm(doc=4408)
         0.09719525 = weight(abstract_txt:theory in 4408) [ClassicSimilarity], result of:
           0.09719525 = score(doc=4408,freq=2.0), product of:
             0.242756 = queryWeight, product of:
               3.232322 = boost
               4.529811 = idf(docFreq=1301, maxDocs=44421)
               0.016579647 = queryNorm
             0.4003825 = fieldWeight in 4408, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               4.529811 = idf(docFreq=1301, maxDocs=44421)
               0.0625 = fieldNorm(doc=4408)
       0.2 = coord(5/25)
   

5. Chaitin, G.J.: ¬The limits of mathematics (1997) 0.07

   0.07336346 = sum of:
     0.07336346 = product of:
       0.61136216 = sum of:
         0.032374747 = weight(abstract_txt:information in 974) [ClassicSimilarity], result of:
           0.032374747 = score(doc=974,freq=2.0), product of:
             0.086527765 = queryWeight, product of:
               2.1575575 = boost
               2.4188995 = idf(docFreq=10748, maxDocs=44421)
               0.016579647 = queryNorm
             0.37415442 = fieldWeight in 974, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               2.4188995 = idf(docFreq=10748, maxDocs=44421)
               0.109375 = fieldNorm(doc=974)
         0.17009169 = weight(abstract_txt:theory in 974) [ClassicSimilarity], result of:
           0.17009169 = score(doc=974,freq=2.0), product of:
             0.242756 = queryWeight, product of:
               3.232322 = boost
               4.529811 = idf(docFreq=1301, maxDocs=44421)
               0.016579647 = queryNorm
             0.70066935 = fieldWeight in 974, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               4.529811 = idf(docFreq=1301, maxDocs=44421)
               0.109375 = fieldNorm(doc=974)
         0.40889573 = weight(abstract_txt:algorithmic in 974) [ClassicSimilarity], result of:
           0.40889573 = score(doc=974,freq=1.0), product of:
             0.4986778 = queryWeight, product of:
               4.0120864 = boost
               7.496775 = idf(docFreq=66, maxDocs=44421)
               0.016579647 = queryNorm
             0.81995976 = fieldWeight in 974, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.496775 = idf(docFreq=66, maxDocs=44421)
               0.109375 = fieldNorm(doc=974)
       0.12 = coord(3/25)